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.

Right Angle Crossing Graphs and 1-planarity

LIOTTA, Giuseppe
2012

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.
2012
9783642258770
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/912397
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 9
social impact