Bounded embeddings of graphs in the plane Conference Paper


Author(s): Fulek, Radoslav
Title: Bounded embeddings of graphs in the plane
Title Series: LNCS
Affiliation IST Austria
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.
Keywords: Algebraic crossing number; C-planarity; Graph planarity testing; PQ-tree; Weakly simple embedding
Conference Title: IWOCA: International Workshop on Combinatorial Algorithms
Volume: 9843
Conference Dates: August 17 - 19, 2016
Conference Location: Helsinki, Finland
ISBN: 978-331944542-7
Publisher: Springer  
Date Published: 2016-08-09
Start Page: 31
End Page: 42
Sponsor: The research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007-2013) under REA grant agreement no [291734].
URL:
DOI: 10.1007/978-3-319-44543-4_3
Open access: yes (repository)
IST Austria Authors
  1. Radoslav Fulek
    7 Fulek
Related IST Austria Work