Right Angle Crossing Graphs and 1PlanarityEades, Peter and Liotta, Giuseppe (2012) Right Angle Crossing Graphs and 1Planarity. In: Graph Drawing 19th International Symposium, GD 2011, September 2123, 2011 , pp. 148153(Official URL: http://dx.doi.org/10.1007/9783642258787_15). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642258787_15
AbstractA Right Angle Crossing Graph (also called RAC graph for short) is a graph that has a straightline drawing where any two crossing edges are orthogonal to each other. A 1planar graph is a graph that has a drawing where every edge is crossed at most once. We study the relationship between RAC graphs and 1planar 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 1planar. Also, we show that for every integer i such that i ≥ 0, there exists a 1planar graph with n = 8 + 4i vertices and 4n − 10 edges that is not a RAC graph.
Actions (login required)
