Author(s):

Fulek, Radoslav; Pelsmajer, Michael J; Schaefer, Marcus

Title: 
HananiTutte 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 crossingfree 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 HananiTutte 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 1921, 2016

Conference Location:

Athens, Greece

ISBN:

9783319272603

Publisher:

Springer

Date Published:

20160101

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/20072013) under REA grant agreement no [291734].

URL: 

DOI: 
10.1007/9783319501062_36

Open access: 
yes (repository) 