Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs

Alam, Muhammed Jawaherul and Brandenburg, Franz J. and Kobourov, Stephen G. (2013) Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 83-94(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_8).

Full text not available from this repository.

Abstract

A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. In general, 1-planar graphs do not admit straight-line drawings. We show that every 3-connected 1-planar graph has a straight-line drawing on an integer grid of quadratic size, with the exception of a single edge on the outer face that has one bend. The drawing can be computed in linear time from any given 1-planar embedding of the graph.

Item Type:	Conference Paper
Classifications:	G Algorithms and Complexity > G.420 Crossings P Styles > P.720 Straight-line
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/1363

Actions (login required)

View Item