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 xbounded 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 xbounded embedding.Then we present an efficient algorithm, which relies on our result, for testing the existence of an xbounded 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 cplanarity testing of flat clustered graphs with three clusters is tractable when the underlying abstract graph is a forest.

Keywords: 
Algebraic crossing number; Cplanarity; Graph planarity testing; PQtree; Weakly simple embedding

Conference Title:

IWOCA: International Workshop on Combinatorial Algorithms

Volume: 
9843

Conference Dates:

August 17  19, 2016

Conference Location:

Helsinki, Finland

ISBN:

9783319445427

Publisher:

Springer

Date Published:

20160809

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/20072013) under REA grant agreement no [291734].

URL: 

DOI: 
10.1007/9783319445434_3

Open access: 
yes (repository) 