Right Angle Crossing Graphs and 1-Planarity

Eades, Peter and Liotta, Giuseppe (2012) Right Angle Crossing Graphs and 1-Planarity. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011 , pp. 148-153(Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_15).

Full text not available from this repository.

Abstract

A Right Angle Crossing Graph (also called RAC graph for short) is a graph that has a straight-line drawing where any two crossing edges are orthogonal to each other. A 1-planar graph is a graph that has a drawing where every edge is crossed at most once. We study the relationship between RAC graphs and 1-planar graphs in the extremal case that the RAC graphs have as many edges as possible. It is known that a maximally dense RAC graph with n > 3 vertices has 4n − 10 edges. We show that every maximally dense RAC graph is 1-planar. Also, we show that for every integer i such that i ≥ 0, there exists a 1-planar graph with n = 8 + 4i vertices and 4n − 10 edges that is not a RAC graph.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-25878-7_15
Classifications: G Algorithms and Complexity > G.420 Crossings
P Styles > P.999 Others
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1249

Actions (login required)

View Item View Item