Fan-planarity: properties and complexity
From MaRDI portal
Publication:2346379
DOI10.1016/j.tcs.2015.04.020zbMath1317.68134arXiv1406.5299OpenAlexW1479684016MaRDI QIDQ2346379
Fabrizio Montecchiani, Emilio Di Giacomo, Maurizio Patrignani, Walter Didimo, Antonios Symvonis, Carla Binucci, Ioannis. G. Tollis
Publication date: 1 June 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1406.5299
Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
The density of fan-planar graphs, Simplifying Non-Simple Fan-Planar Drawings, Simplifying non-simple fan-planar drawings, Recognizing and embedding simple optimal 2-planar graphs, On fan-crossing and fan-crossing free graphs, Fan-crossing free graphs and their relationship to other beyond-planar graphs, On the recognition of fan-planar and maximal outer-fan-planar graphs, The family of fan-planar graphs, Shallow Minors, Graph Products, and Beyond-Planar Graphs, On fan-crossing graphs, Recognizing optimal 1-planar graphs in linear time, Efficient generation of different topological representations of graphs beyond-planarity, 1-fan-bundle-planar drawings of graphs, Gap-Planar Graphs, A linear-time algorithm for testing full outer-2-planarity, Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity, Simple \(k\)-planar graphs are simple \((k + 1)\)-quasiplanar, Characterizing 5-map graphs by 2-fan-crossing graphs, Unnamed Item, Gap-planar graphs, On Aligned Bar 1-Visibility Graphs, Beyond Planar Graphs: Introduction, Fan-Planar Graphs, 1-planarity testing and embedding: an experimental study, 2-Layer k-Planar Graphs
Cites Work
- 1-planarity of complete multipartite graphs
- 2-layer right angle crossing drawings
- Area, curve complexity, and crossing resolution of non-planar graph drawings
- Drawing graphs with right angle crossings
- On the maximum number of edges in quasi-planar graphs
- Confluent layered drawings
- On the maximum number of edges in topological graphs with no four pairwise crossing edges
- Optimal 1-planar graphs which triangulate other surfaces
- Graphs drawn with few crossings per edge
- Quasi-planar graphs have a linear number of edges
- On geometric graphs with no \(k\) pairwise parallel edges
- Density of straight-line 1-planar graph drawings
- Right angle crossing graphs and 1-planarity
- The graph crossing number and its variants: a survey
- Area requirement of graph drawings with few crossings per edge
- Algorithms for graphs embeddable with few crossings per edge
- The Crossing-Angle Resolution in Graph Drawing
- A Linear-Time Algorithm for Testing Outer-1-Planarity
- Straight-Line Grid Drawings of 3-Connected 1-Planar Graphs
- Recognizing Outer 1-Planar Graphs in Linear Time
- On the Number of Edges of Fan-Crossing Free Graphs
- Graphs That Admit Polyline Drawings with Few Crossing Angles
- Fáry’s Theorem for 1-Planar Graphs
- Fan-Planar Graphs: Combinatorial Properties and Complexity Results
- On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs
- Re-embeddings of Maximum 1-Planar Graphs
- Über 1-optimale Graphen
- Crossing Number is NP-Complete
- Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way
- Minimal Obstructions for 1-Immersions and Hardness of 1-Planarity Testing
- The crossing number ofK1,3,n andK2,3,n
- Large Angle Crossing Drawings of Planar Graphs in Subquadratic Area
- On the Density of Maximal 1-Planar Graphs
- h-Quasi Planar Drawings of Bounded Treewidth Graphs in Linear Area
- EVERY OUTER-1-PLANE GRAPH HAS A RIGHT ANGLE CROSSING DRAWING
- The Number of Edges in $k$-Quasi-planar Graphs
- Notes on large angle crossing graphs
