Hanani-Tutte for radial planarity II Conference Paper

Author(s): Fulek, Radoslav; Pelsmajer, Michael J; Schaefer, Marcus
Title: Hanani-Tutte for radial planarity II
Title Series: LNCS
Affiliation IST Austria
Abstract: A drawing of a graph G is radial if the vertices of G are placed on concentric circles C1, … , Ck with common center c, and edges are drawn radially: every edge intersects every circle centered at c at most once. G is radial planar if it has a radial embedding, that is, a crossing-free radial drawing. If the vertices of G are ordered or partitioned into ordered levels (as they are for leveled graphs), we require that the assignment of vertices to circles corresponds to the given ordering or leveling. A pair of edges e and f in a graph is independent if e and f do not share a vertex. We show that a graph G is radial planar if G has a radial drawing in which every two independent edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the strong Hanani-Tutte theorem for radial planarity. This characterization yields a very simple algorithm for radial planarity testing.
Keywords: visualization; Planarity; Concentric circles; Graph G; Radial drawings; Engineering controlled terms: drawing (graphics); engineering main heading: graph theory; independent edges; SIMPLE algorithm
Conference Title: GD: Graph Drawing and Network Visualization
Volume: 9801
Conference Dates: September 19-21, 2016
Conference Location: Athens, Greece
ISBN: 978-331927260-3
Publisher: Springer  
Date Published: 2016-01-01
Start Page: 468
End Page: 481
Sponsor: R. Fulek—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].
DOI: 10.1007/978-3-319-50106-2_36
Open access: yes (repository)
IST Austria Authors
  1. Radoslav Fulek
    14 Fulek
Related IST Austria Work