Hanani-Tutte for Radial Planarity II

Fulek, Radoslav and Pelsmajer, Michael J. and Schaefer, Marcus (2016) Hanani-Tutte for Radial Planarity II. In: Graph Drawing and Network Visualization. GD 2016, September, 19. - 21., 2016 , pp. 468-481(Official URL: http://dx.doi.org/10.1007/978-3-319-50106-2_36).

Full text not available from this repository.

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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.420 Crossings
Z Theory > Z.750 Topology
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1563

Actions (login required)

View Item View Item