Hanani-Tutte for Radial Planarity

Fulek, Radoslav and Pelsmajer, Michael J. and Schaefer, Marcus (2015) Hanani-Tutte for Radial Planarity. In: Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, September 24-26, 2015 , pp. 99-110(Official URL: http://dx.doi.org/10.1007/978-3-319-27261-0_9).

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. 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.

Item Type: Conference Paper
Classifications: P Styles > P.480 Layered
P Styles > P.540 Planar
P Styles > P.660 Radial
Z Theory > Z.750 Topology
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 04 May 2016 16:17
Last Modified: 23 Jun 2016 11:35
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1481

Actions (login required)

View Item View Item