On fan-crossing graphs

DOI10.1016/J.TCS.2020.07.002MaRDI QIDQ2202017zbMATHOpenAlexFDO

Authors Franz J. Brandenburg

Publication date 17 September 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graph drawingfansindependent edgesedge crossings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: A fan is a set of edges with a single common endpoint. A graph is fan-crossing if it admits a drawing in the plane so that each edge is crossed by edges of a fan. It is fan-planar if, in addition, the common endpoint is on the same side of the crossed edge. A graph is adjacency-crossing if it admits a drawing so that crossing edges are adjacent. Then it excludes independent crossings which are crossings by edges with no common endpoint. Adjacency-crossing allows triangle-crossings in which an edge crosses the edges of a triangle, which is excluded at fan-crossing graphs. We show that every adjacency-crossing graph is fan-crossing. Thus triangle-crossings can be avoided. On the other hand, there are fan-crossing graphs that are not fan-planar, whereas for every fan-crossing graph there is a fan-planar graph on the same set of vertices and with the same number of edges. Hence, fan-crossing and fan-planar graphs are different, but they do not differ in their density with at most 5n - 10 edges for graphs of size n.

Recommendations

• On fan-crossing and fan-crossing free graphs
• Fan-crossing free graphs and their relationship to other beyond-planar graphs
• On fans in multigraphs
• Fan-planar graphs
• On the spanning fan-connectivity of graphs
• Crossing graphs of fiber-complemented graphs
• Crossing graphs of fiber-complemented graphs
• Fan-planar graphs: combinatorial properties and complexity results

Cites work

• scientific article; zbMATH DE number 434700 (Why is no real title available?)
• A first order logic definition of beyond-planar graphs
• An annotated bibliography on 1-planarity
• Ein Sechsfarbenproblem auf der Kugel
• Fan-planarity: properties and complexity
• On fan-crossing and fan-crossing free graphs
• On grids in topological graphs
• On the density of maximal 1-planar graphs
• On the maximum number of edges in quasi-planar graphs
• On the recognition of fan-planar and maximal outer-fan-planar graphs
• Quasi-planar graphs have a linear number of edges
• Recognizing optimal 1-planar graphs in linear time
• Topological graphs with no large grids

Cited in

(14)

• Crossing numbers of beyond-planar graphs
• scientific article; zbMATH DE number 5234236 (Why is no real title available?)
• Efficient generation of different topological representations of graphs beyond-planarity
• The family of fan-planar graphs
• Crossing graphs of fiber-complemented graphs
• Simplifying non-simple fan-planar drawings
• On optimal beyond-planar graphs
• On fan-crossing and fan-crossing free graphs
• Characterizing 5-map graphs by 2-fan-crossing graphs
• Compatibility fans for graphical nested complexes
• Simplifying Non-Simple Fan-Planar Drawings
• Fan-crossing free graphs and their relationship to other beyond-planar graphs
• The density of fan-planar graphs
• Straight-line drawings of 1-planar graphs

This page was built for publication: On fan-crossing graphs

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