Bounded embeddings of graphs in the plane
Fulek R. 2016. Bounded embeddings of graphs in the plane. IWOCA: International Workshop on Combinatorial Algorithms, LNCS, vol. 9843, 31–42.
Download (ext.)
https://arxiv.org/abs/1610.07144
[Preprint]
Conference Paper
| Published
| English
Scopus indexed
Author
Department
Series Title
LNCS
Abstract
A drawing in the plane (ℝ2) of a graph G = (V,E) equipped with a function γ : V → ℕ is x-bounded if (i) x(u) < x(v) whenever γ(u) < γ(v) and (ii) γ(u) ≤ γ(w) ≤ γ(v), where uv ∈ E and γ(u) ≤ γ(v), whenever x(w) ∈ x(uv), where x(.) denotes the projection to the xaxis.We prove a characterization of isotopy classes of embeddings of connected graphs equipped with γ in the plane containing an x-bounded embedding.Then we present an efficient algorithm, which relies on our result, for testing the existence of an x-bounded embedding if the given graph is a forest.This partially answers a question raised recently by Angelini et al.and Chang et al., and proves that c-planarity testing of flat clustered graphs with three clusters is tractable when the underlying abstract graph is a forest.
Publishing Year
Date Published
2016-08-09
Publisher
Springer
Volume
9843
Page
31 - 42
Conference
IWOCA: International Workshop on Combinatorial Algorithms
Conference Location
Helsinki, Finland
Conference Date
2016-08-17 – 2018-08-19
IST-REx-ID
Cite this
Fulek R. Bounded embeddings of graphs in the plane. In: Vol 9843. Springer; 2016:31-42. doi:10.1007/978-3-319-44543-4_3
Fulek, R. (2016). Bounded embeddings of graphs in the plane (Vol. 9843, pp. 31–42). Presented at the IWOCA: International Workshop on Combinatorial Algorithms, Helsinki, Finland: Springer. https://doi.org/10.1007/978-3-319-44543-4_3
Fulek, Radoslav. “Bounded Embeddings of Graphs in the Plane,” 9843:31–42. Springer, 2016. https://doi.org/10.1007/978-3-319-44543-4_3.
R. Fulek, “Bounded embeddings of graphs in the plane,” presented at the IWOCA: International Workshop on Combinatorial Algorithms, Helsinki, Finland, 2016, vol. 9843, pp. 31–42.
Fulek R. 2016. Bounded embeddings of graphs in the plane. IWOCA: International Workshop on Combinatorial Algorithms, LNCS, vol. 9843, 31–42.
Fulek, Radoslav. Bounded Embeddings of Graphs in the Plane. Vol. 9843, Springer, 2016, pp. 31–42, doi:10.1007/978-3-319-44543-4_3.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access