Hanani-Tutte for Radial Planarity II
A drawing of a graph G is radial if the vertices of G are placed on concentric circles \(C_1, \ldots , C_k\) 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
- PDF / 456,347 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 114 Downloads / 228 Views
IST Austria, Am Campus 1, 3400 Klosterneuburg, Austria [email protected] 2 Illinois Institute of Technology, Chicago, IL 60616, USA [email protected] 3 DePaul University, Chicago, IL 60604, USA [email protected]
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.
1
Introduction
This paper continues work begun in “Hanani-Tutte for Radial Planarity” [16] by the same authors; to make the current paper self-contained we repeat some of the background and terminological exposition from the previous paper. In a leveled graph every vertex is assigned a level in {1, . . . , k}. A radial drawing visualizes the leveling of the graph by placing the vertices on concentric circles corresponding to the levels of G. Edges must be drawn as radial curves: for any circle concentric with the others, a radial curve intersects the circle at most once. A leveled graph is radial planar if it admits a radial embedding, that is, a radial drawing without crossings. The concept of radial planarity generalizes level planarity [8] in which levels are parallel lines instead of concentric circles (radially-drawn edges are replaced with x-monotone edges). A version of the paper containing all proofs is available on arxiv. 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]. c Springer International Publishing AG 2016 Y. Hu and M. N¨ ollenburg (Eds.): GD 2016, LNCS 9801, pp. 468–481, 2016. DOI: 10.1007/978-3-319-50106-2 36
Hanani-Tutte for Radial Planarity II
469
We previously established the weak Hanani-Tutte theorem for radial planarity: a leveled graph G is radial planar if it has a radial drawing (respecting the leveling) in which every two edges cross an even number of times [16, Theorem 1]. Our main result is the following strengthening of the weak Hanani-Tutte theorem for radial planarity, also generalizing the strong HananiTutte theorem for level-planarity [15]: Theorem 1. If a leveled graph has a radial drawing in which every two independent edges c
Data Loading...
