Hanani-Tutte for radial planarity Conference Paper

Author(s): Fulek, Radoslav; Pelsmajer, Michael J; Schaefer, Marcus
Title: Hanani-Tutte for radial planarity
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. We show that a graph G is radial planar if G has a radial drawing in which every two edges cross an even number of times; the radial embedding has the same leveling as the radial drawing. In other words, we establish the weak variant of the Hanani-Tutte theorem for radial planarity. This generalizes a result by Pach and Tóth.
Keywords: Planarity; Concentric circles; Graph G; Radial drawings
Conference Title: GD: Graph Drawing and Network Visualization
Volume: 9411
Conference Dates: September 24-26, 2015
Conference Location: Los Angeles, CA, USA
ISBN: 978-331927260-3
Publisher: Springer  
Date Published: 2015-11-27
Start Page: 99
End Page: 110
DOI: 10.1007/978-3-319-27261-0_9
Notes: 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].
Open access: yes (repository)
IST Austria Authors
  1. Radoslav Fulek
    14 Fulek
Related IST Austria Work