Quasi-planar graphs have a linear number of edges

No abstract is available for this paper.

• Publication year

  1995

• Venue

  International Symposium Graph Drawing and Network Visualization

• Publication date

  1995-09-20

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/BFb0021784
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Combinatorial geometry

  1995cited by this paper
• Applications of the crossing number

  1994cited by this paper
• A turán-type theorem on chords of a convex polygon

  1992influential reference
• Covering and coloring problems for relatives of intervals

  1985cited by this paper
• On the chromatic number of multiple interval graphs and overlap graphs

  1985cited by this paper
• Algorithmic Graph Theory

  1985cited by this paper

• Cross-free families have linear size

  2026cites this paper
• Optimal right angles crossing graphs

  2026cites this paper
• Minimum Plane Bichromatic Spanning Trees

  2024cites this paper
• Tight bounds for intersection‐reverse sequences, edge‐ordered graphs, and applications

  2024cites this paper
• Parameterized Algorithms for Beyond-Planar Crossing Numbers

  2024cites this paper
• Note on Min-k-Planar Drawings of Graphs

  2024cites this paper
• Proposing a Pure Binary Linear Programming(PBLP) Model to Discover Eulerian Circuits in Complete Graphs

  2023cites this paper
• Min-k-planar Drawings of Graphs

  2023cites this paper
• Axis-Parallel Right Angle Crossing Graphs

  2023cites this paper
• Can an NN model plainly learn planar layouts?

  2022cites this paper
• On Optimal Beyond-Planar Graphs

  2022cites this paper
• -planar graphs simple ( k +

  2022cites this paper
• Non-Crossing Shortest Paths are Covered with Exactly Four Forests

  2022cites this paper
• Quasiplanar graphs, string graphs, and the Erdős-Gallai problem

  2021cites this paper
• Simplifying Non-Simple Fan-Planar Drawings

  2021cites this paper
• Quasi-planar Graphs

  2020cites this paper
• Fan-crossing free graphs and their relationship to other beyond-planar graphs

  2020cites this paper
• Beyond Planar Graphs: Introduction

  2020cites this paper
• Beyond Planar Graphs: Communications of NII Shonan Meetings

  2020cites this paper
• 2-Layer k-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth

  2020cites this paper
• Twenty Years of Progress of JCDCG3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\hbox {JCDCG}^3$$\end{document}

  2020cites this paper
• Fan-Crossing Free Graphs

  2020cites this paper
• Packing and Covering Balls in Graphs Excluding a Minor

  2020cites this paper
• On Point Set Embeddings for k-Planar Graphs with Few Bends per Edge

  2019cites this paper
• Graph Drawing and Network Visualization: 27th International Symposium, GD 2019, Prague, Czech Republic, September 17–20, 2019, Proceedings

  2019cites this paper
• Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity

  2019cites this paper
• Planar point sets determine many pairwise crossing segments

  2019cites this paper
• Simple k-Planar Graphs are Simple (k+1)-Quasiplanar

  2019cites this paper
• The QuaSEFE Problem

  2019cites this paper
• A linear-time algorithm for testing full outer-2-planarity

  2019cites this paper
• Beyond-Planarity: Turán-Type Results for Non-Planar Bipartite Graphs

  2018cites this paper
• On RAC Drawings of Graphs with one Bend per Edge

  2018cites this paper
• Coloring Curves that Cross a Fixed Curve

  2018cites this paper
• Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs

  2018cites this paper
• A First Order Logic Definition of Beyond-Planar Graphs

  2018influential citation
• On the Size of K-Cross-Free Families

  2018cites this paper
• Two-Planar Graphs Are Quasiplanar

  2017cites this paper
• Beyond-Planar Graphs : Algorithmics and Combinatorics

  2017cites this paper
• Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count

  2017cites this paper
• 1-Fan-Bundle-Planar Drawings of Graphs

  2017cites this paper
• On the Size of K-Cross-Free Families

  2017cites this paper
• 1 Sum of Square Roots by Tillmann Miltzow

  2017influential citation
• Area-Thickness Trade-Offs for Straight-Line Drawings of Planar Graphs

  2017cites this paper
• 10 GEOMETRIC GRAPH THEORY

  2017cites this paper
• On Fan-Crossing Graphs

  2017cites this paper
• Beyond-Planarity: Density Results for Bipartite Graphs

  2017cites this paper
• On the Relationship between k-Planar and k-Quasi Planar Graphs

  2017cites this paper
• A Simple Quasi-planar Drawing of K10

  2016cites this paper
• Proceedings of the 28th Canadian Conference on Computational Geometry, CCCG 2016, August 3-5, 2016, Simon Fraser University, Vancouver, British Columbia, Canada

  2016cites this paper
• 10 GEOMETRIC GRAPH THEORY János Pach

  2016cites this paper
• Re-embedding a 1-Plane Graph into a Straight-Line Drawing in Linear Time

  2016cites this paper
• On the Density of 3-Planar Graphs

  2016cites this paper
• Bounding extremal functions of forbidden 0-1 matrices using (r, s)-formations

  2016cites this paper
• Path-Additions of Graphs

  2016cites this paper
• On the Density of Non-simple 3-Planar Graphs

  2016cites this paper
• A Faster Algorithm for the Minimum Red-Blue-Purple Spanning Graph Problem for Points on a Circle

  2016cites this paper
• Minimum Weight Connectivity Augmentation for Planar Straight-Line Graphs

  2016cites this paper
• Coloring Curves that Cross a Fixed Curve

  2015cites this paper
• Recognizing and drawing IC-planar graphs

  2015cites this paper
• Angular Schematization in Graph Drawing

  2015cites this paper
• Lecture Notes Geometric Graph Theory

  2015cites this paper
• On the Size of Planarly Connected Crossing Graphs

  2015cites this paper
• On 4-Map Graphs and 1-Planar Graphs and their Recognition Problem

  2015cites this paper
• Coloring segment intersection graphs avoiding monochromatic cliques Proposer :

  2015cites this paper
• On Bar (1, j)-Visibility Graphs - (Extended Abstract)

  2015cites this paper
• Planar and Quasi-Planar Simultaneous Geometric Embedding

  2014cites this paper
• The Maximum Number of Edges in Geometric Graphs with Pairwise Virtually Avoiding Edges

  2014cites this paper
• Fan-planarity: Properties and complexity

  2014cites this paper
• Covering Nearly Surface-Embedded Graphs with a Fixed Number of Balls

  2014cites this paper
• On-Line Approach to Off-Line Coloring Problems on Graphs with Geometric Representations

  2014cites this paper
• On the Recognition of Fan-Planar and Maximal Outer-Fan-Planar Graphs

  2014cites this paper
• The Density of Fan-Planar Graphs

  2014cites this paper
• Geometric Intersection Patterns and the Theory of Topological Graphs 3 Using similar ideas

  2014cites this paper
• Fan-Planar Graphs: Combinatorial Properties and Complexity Results

  2014cites this paper
• A Survey of Visualization Tools Assessed for Anomaly-Based Intrusion Detection Analysis

  2014cites this paper
• Planar and Quasi Planar Simultaneous Geometric Embedding (cid:2)

  2014cites this paper
• Covering Nearly Surface-Embedded Graphs with a Fixed Number of Balls

  2014cites this paper
• Outerstring graphs are χ-bounded

  2013cites this paper
• Applications of a New Separator Theorem for String Graphs

  2013cites this paper
• The Beginnings of Geometric Graph Theory

  2013cites this paper
• A Guide to the Discharging Method

  2013cites this paper
• On the edge crossing properties of Euclidean minimum weight Laman graphs

  2013cites this paper
• Drawings of Graphs

  2013cites this paper
• New bounds on the maximum number of edges in k-quasi-planar graphs

  2013cites this paper
• On the Number of Edges of Fan-Crossing Free Graphs

  2013cites this paper
• The Maximum Number of Edges in Geometric Graphs with Pairwise Virtually Avoiding Edges

  2013cites this paper
• Outerstring graphs are $\chi$-bounded

  2013cites this paper
• An Upper Bound on the Number of Edges in an Almost Planar Bipartite Graph

  2013cites this paper
• Nearly Planar Graphs and {\lambda}-flat Graphs

  2013cites this paper
• Binoculars: Comprehending Open Source Projects through Graphs

  2012cites this paper
• Construction of Locally Plane Graphs with Many Edges

  2011cites this paper
• The Number of Edges in k-Quasi-planar Graphs

  2011cites this paper
• $k$-quasi Planar Graphs

  2011cites this paper
• On disjoint crossing families in geometric graphs

  2010cites this paper
• Drawing graphs with right angle crossings

  2009cites this paper
• Notes on Large Angle Crossing Graphs

  2009cites this paper
• The discharging method in combinatorial geometry and the Pach – Sharir conjecture

  2009cites this paper
• Connected Feedback Vertex Set in Planar Graphs

  2009cites this paper
• A Linear Kernel for Planar Feedback Vertex Set

  2008cites this paper
• Erdős-Hajnal-type Results on Intersection Patterns of Geometric Objects

  2008cites this paper