Improved enumeration of simple topological graphs

DOI10.1007/S00454-013-9535-8zbMATH Open1275.05027arXiv1212.2950OpenAlexW2051741215MaRDI QIDQ377494FDOQ377494

Authors: Jan Kynčl 

Publication date: 6 November 2013

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

Abstract: A simple topological graph T = (V(T), E(T)) is a drawing of a graph in the plane where every two edges have at most one common point (an endpoint or a crossing) and no three edges pass through a single crossing. Topological graphs G and H are isomorphic if H can be obtained from G by a homeomorphism of the sphere, and weakly isomorphic if G and H have the same set of pairs of crossing edges. We generalize results of Pach and Toth and the author's previous results on counting different drawings of a graph under both notions of isomorphism. We prove that for every graph G with n vertices, m edges and no isolated vertices the number of weak isomorphism classes of simple topological graphs that realize G is at most 2^O(n^2 log(m/n)), and at most 2^O(mn^{1/2} log n) if m < n^{3/2}. As a consequence we obtain a new upper bound 2^O(n^{3/2} log n) on the number of intersection graphs of n pseudosegments. We improve the upper bound on the number of weak isomorphism classes of simple complete topological graphs with n vertices to 2^{n^2 alpha(n)^O(1)}, using an upper bound on the size of a set of permutations with bounded VC-dimension recently proved by Cibulka and the author. We show that the number of isomorphism classes of simple topological graphs that realize G is at most 2^{m^2+O(mn)} and at least 2^Omega(m^2) for graphs with m > (6+epsilon)n.

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

Recommendations

• Enumeration of simple complete topological graphs
• Enumeration of simple complete topological graphs
• On edges crossing few other edges in simple topological complete graphs
• Graph Drawing
• Saturated simple and 2-simple topological graphs with few edges

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

• A Census of Planar Maps
• On the number of arrangements of pseudolines
• Title not available (Why is that?)
• The Distribution of Crossings of Chords Joining Pairs of 2n Points on a Circle
• Graphs with maximal number of adjacent pairs of edges
• Title not available (Why is that?)
• Lower Bounds for Approximation by Nonlinear Manifolds
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Enumeration of simple complete topological graphs
• Counting rooted maps by genus. III: Nonseparable maps
• 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
• Enumeration of 2-connected loopless 4-regular maps on the plane
• Unavoidable configurations in complete topological graphs
• The sum of the squares of degrees: sharp asymptotics
• Universal exponents and tail estimates in the enumeration of planar maps
• Title not available (Why is that?)
• Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
• Sum of squares of degrees in a graph
• Title not available (Why is that?)
• On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm
• Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
• Title not available (Why is that?)
• Title not available (Why is that?)
• Maximizing Several Cuts Simultaneously
• The enumeration of c-nets via quadrangulations
• Contribution a L'etude Du Probleme Des Timbres Poste
• Graph-Theoretic Concepts in Computer Science
• Recognizing string graphs in NP
• VC-dimension of sets of permutations
• Enumerating near-4-regular maps on the sphere and the torus
• Simple realizability of complete abstract topological graphs in P
• Coding and counting arrangements of pseudolines
• How many ways can one draw a graph?

Cited In (18)

• Title not available (Why is that?)
• Closing in on Hill's conjecture
• Complete graph drawings up to triangle mutations
• Efficient generation of different topological representations of graphs beyond-planarity
• Enumeration of simple complete topological graphs
• Discrete geometry. Abstracts from the workshop held January 21--26, 2024
• Different types of isomorphisms of drawings of complete multipartite graphs
• Topological drawings meet classical theorems from convex geometry
• Saturated simple and \(k\)-simple topological graphs
• Inserting one edge into a simple drawing is hard
• Unavoidable patterns in complete simple topological graphs
• Shellable drawings and the cylindrical crossing number of \(K_n\)
• Simple realizability of complete abstract topological graphs simplified
• On plane subgraphs of complete topological drawings
• Unavoidable patterns in complete simple topological graphs
• Efficient generation of different topological representations of graphs beyond-planarity
• Extending simple drawings
• On the edge-vertex ratio of maximal thrackles

This page was built for publication: Improved enumeration of simple topological graphs

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