The study of nonplanar drawings of graphs with restricted crossing configurations is a well-established topic in graph drawing, often referred to as beyond-planar graph drawing. One of the most studied types of drawings in this area are the k-planar drawings (k>= 1 ), where each edge cannot cross more than k times. We generalize k-planar drawings, by introducing the new family of min-k-planar drawings. In a min-k-planar drawing edges can cross an arbitrary number of times, but for any two crossing edges, one of the two must have no more than k crossings. We prove a general upper bound on the number of edges of min-k-planar drawings, a finer upper bound for k= 3, and tight upper bounds for k= 1, 2. Also, we study the inclusion relations between min-k-planar graphs (i.e., graphs admitting min-k-planar drawings) and k-planar graphs.

Min-k-planar Drawings of Graphs

Binucci C.
;
Didimo W.
;
Liotta G.
;
Tappini A.
2023

Abstract

The study of nonplanar drawings of graphs with restricted crossing configurations is a well-established topic in graph drawing, often referred to as beyond-planar graph drawing. One of the most studied types of drawings in this area are the k-planar drawings (k>= 1 ), where each edge cannot cross more than k times. We generalize k-planar drawings, by introducing the new family of min-k-planar drawings. In a min-k-planar drawing edges can cross an arbitrary number of times, but for any two crossing edges, one of the two must have no more than k crossings. We prove a general upper bound on the number of edges of min-k-planar drawings, a finer upper bound for k= 3, and tight upper bounds for k= 1, 2. Also, we study the inclusion relations between min-k-planar graphs (i.e., graphs admitting min-k-planar drawings) and k-planar graphs.
2023
978-3-031-49271-6
978-3-031-49272-3
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/1568536
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact