HananiTutte for Radial Planarity IIFulek, Radoslav and Pelsmajer, Michael J. and Schaefer, Marcus (2016) HananiTutte for Radial Planarity II. In: Graph Drawing and Network Visualization. GD 2016, September, 19.  21., 2016 , pp. 468481(Official URL: http://dx.doi.org/10.1007/9783319501062_36). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319501062_36
AbstractA 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.
Actions (login required)
