Graphs with at most one crossing

DOI10.1016/J.DISC.2019.06.031MaRDI QIDQ2324508zbMATH OpenOpenAlexFDO

Authors André C. Silva, Alan Arroyo, R. B. Richter, Orlando Lee

Publication date 11 September 2019

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.09955

zbMATH Keywords

crossing number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: The crossing number of a graph $G$ is the least number of crossings over all possible drawings of $G$. We present a structural characterization of graphs with crossing number one.

Recommendations

• Crossing numbers
• On the join graphs with crossing number one
• Do we really understand the crossing numbers?
• On graphs whose line graphs have crossing number one
• The crossing number of the generalized Petersen graph \(P [3k - 1,k]\)

Cites work

• 2-linked graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• Characterizing 2-crossing-critical graphs
• Characterizing graphs with crossing number at least 2
• Construction of crossing-critical graphs
• Crossing numbers
• Cubic graphs with crossing number two
• Disjoint paths in graphs
• Edges and Kuratowski Subgraphs of Non-Planar Graphs
• Graph minors. IX: Disjoint crossed paths
• scientific article; zbMATH DE number 3829947 (Why is no real title available?)
• scientific article; zbMATH DE number 1482227 (Why is no real title available?)
• Infinite families of crossing-critical graphs with a given crossing number
• Large non-planar graphs and an application to crossing-critical graphs
• On a problem of P. Turan concerning graphs
• On graphs whose line graphs have crossing number one
• On Line Graphs with Crossing Number 1
• Separation of vertices by a circuit

Cited in

(8)

• Nonplanarity of iterated line graphs
• On graphs whose line graphs have crossing number one
• GRAPHS WITH ONE HOLE AND COMPETITION NUMBER ONE
• Crossing numbers
• scientific article; zbMATH DE number 3954949 (Why is no real title available?)
• scientific article; zbMATH DE number 475621 (Why is no real title available?)
• On the join graphs with crossing number one
• Domination and independence number of large 2-crossing-critical graphs

This page was built for publication: Graphs with at most one crossing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2324508)