Improved enumeration of simple topological graphs

DOI10.1007/s00454-013-9535-8zbMath1275.05027arXiv1212.2950OpenAlexW2051741215MaRDI QIDQ377494

Jan Kynčl

Publication date: 6 November 2013

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

isomorphism of topological graphssimple complete topological graphsimple topological graphweak isomorphism of topological graphs

Mathematics Subject Classification ID

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

Related Items

Complete graph drawings up to triangle mutations ⋮ Simple realizability of complete abstract topological graphs simplified ⋮ Topological drawings meet classical theorems from convex geometry ⋮ Unavoidable patterns in complete simple topological graphs ⋮ Extending simple drawings ⋮ Efficient generation of different topological representations of graphs beyond-planarity ⋮ On the edge-vertex ratio of maximal thrackles ⋮ Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity ⋮ On plane subgraphs of complete topological drawings ⋮ Shellable drawings and the cylindrical crossing number of \(K_n\) ⋮ Inserting one edge into a simple drawing is hard ⋮ Closing in on Hill's Conjecture ⋮ Unnamed Item ⋮ Saturated simple and \(k\)-simple topological graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Simple realizability of complete abstract topological graphs in P
• Coding and counting arrangements of pseudolines
• How many ways can one draw a graph?
• On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture
• Localized and compact data-structure for comparability graphs
• The number of loopless planar maps
• A survey of the asymptotic behaviour of maps
• Edges without crossings in drawings of complete graphs
• Counting rooted maps by genus. III: Nonseparable maps
• Enumeration of 2-connected loopless 4-regular maps on the plane
• On the number of arrangements of pseudolines
• Unavoidable configurations in complete topological graphs
• The sum of the squares of degrees: sharp asymptotics
• Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
• Sum of squares of degrees in a graph
• On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm
• The Distribution of Crossings of Chords Joining Pairs of 2n Points on a Circle
• Graphs with maximal number of adjacent pairs of edges
• Maximizing Several Cuts Simultaneously
• Lower Bounds for Approximation by Nonlinear Manifolds
• The enumeration of c-nets via quadrangulations
• A Census of Planar Maps
• Contribution a L'etude Du Probleme Des Timbres Poste
• Graph-Theoretic Concepts in Computer Science
• Enumeration of simple complete topological graphs
• Recognizing string graphs in NP
• VC-dimension of sets of permutations
• Enumerating near-4-regular maps on the sphere and the torus