Cover Image

An algorithm for estimating the crossing number of dense graphs, and continuous analogs of the crossing and rectilinear crossing numbers

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Solé-Pi, Oriol
Format:	Preprint
Published:	2024
Subjects:	Combinatorics 05C10, 05C85
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the crossing profile of rectilinear drawings of $K_n$
by: Chen, Isaac, et al.
Published: (2025)

The rectilinear local crossing number of $K_n$
by: Ábrego, Bernardo M., et al.
Published: (2015)

Burning numbers via eigenpolytopes -- Hamming graphs, Johnson graphs, and halved cubes
by: Tanaka, Hajime, et al.
Published: (2025)

Book crossing numbers of the complete graph and small local convex crossing numbers
by: Ábrego, Bernardo M., et al.
Published: (2016)

The zero blocking numbers of grid graphs
by: Lin, Hau-Yi, et al.
Published: (2025)

Zero blocking numbers of graphs with complexity results
by: Lin, Hau-Yi, et al.
Published: (2025)

The zero blocking numbers of generalized Kneser graphs and generalized Johnson graphs
by: Lin, Hau-Yi, et al.
Published: (2025)

The total chord length of maximal outerplanar graphs
by: Broadus, Haley, et al.
Published: (2024)

The tropical crossing number of a finite graph
by: Cape, Noah, et al.
Published: (2025)

Classification of polyhedral graphs by numbers of common neighbours
by: Maffucci, Riccardo W.
Published: (2025)

A polynomial algorithm to compute the boxicity and threshold dimension of complements of block graphs
by: Caoduro, Marco, et al.
Published: (2025)

The minimum crossing number and minimum size of maximal 1-plane graphs with given connectivity
by: Ouyang, Zhangdong, et al.
Published: (2025)

A general lower bound for the domination number of cylindrical graphs
by: Carreño, José Juan, et al.
Published: (2018)

Infinite families of planar graphs of a given injective chromatic number
by: Daneels, Matias, et al.
Published: (2024)

Skewness, crossing number and Euler's bound for graphs on surfaces
by: Kainen, Paul C.
Published: (2025)

$\mathcal{O}(VE)$ time algorithms for the Grundy (First-Fit) chromatic number of block graphs and graphs with sufficiently large girth
by: Zaker, Manouchehr
Published: (2024)

The integer $\{2\}$-domination number of grids
by: Lee, Jia-Ying, et al.
Published: (2025)

On the largest chromatic number of $F$-free hypergraphs
by: Wang, Yichen, et al.
Published: (2026)

The maximum number of connected sets in regular graphs
by: Cambie, Stijn, et al.
Published: (2023)

Layered tree-independence number and clique-based separators
by: Dallard, Clément, et al.
Published: (2025)

On the number of small edge-weighted subgraphs
by: Yu, Feng, et al.
Published: (2025)

Genetic algorithm and edge-colorings of complete graphs with connected classes
by: Cervantes-Ojeda, Jorge, et al.
Published: (2024)

On the pebbling numbers of Flower, Blanuša, and Watkins snarks
by: Adauto, Matheus, et al.
Published: (2023)

Vertex-minor Ramsey numbers: exact values and extremal structure
by: Bae, Ji Ho
Published: (2026)

Generating maps on oriented surfaces using the homomorphism principle
by: Brinkmann, Gunnar
Published: (2024)

Graph theoretic and algorithmic aspect of the equitable coloring problem in block graphs
by: Furmańczyk, Hanna, et al.
Published: (2020)

Reconstructing a graph from the distance matrix of its boundary
by: Cáceres, José, et al.
Published: (2024)

$2$-polarity and algorithmic aspects of polarity variants on cograph superclasses
by: Contreras-Mendoza, Fernando Esteban, et al.
Published: (2022)

Three results towards the approximation of special maximum matchings in graphs
by: Mkrtchyan, Vahan
Published: (2024)

Algorithmic releases on the spanning trees of suitable graphs
by: Imbesi, Maurizio, et al.
Published: (2017)

A combinatorial bound on the number of distinct eigenvalues of a graph
by: Allred, Sarah, et al.
Published: (2022)

The 2-domination number of cylindrical graphs
by: Martínez, José Antonio, et al.
Published: (2024)

Uniform Geodesic Drawings of Graphs
by: Lepsveridze, Saba, et al.
Published: (2026)

Regularity and separation for Sierpiński products of graphs
by: Maffucci, Riccardo W.
Published: (2025)

Maximizing the number of integer pairs summing to powers of 2 via graph labeling and solving restricted systems of linear (in)equations
by: Alekseyev, Max A.
Published: (2023)

Minimal obstructions to $C_5$-coloring in hereditary graph classes
by: Goedgebeur, Jan, et al.
Published: (2024)

5-Coloring Planar Graphs with a Color Class of Order at Most $|V|/6$
by: Inoue, Yuta, et al.
Published: (2025)

Common neighbours in planar graphs
by: Maffucci, Riccardo W.
Published: (2025)

Betti number estimates for non-negatively curved graphs
by: Hehl, Moritz, et al.
Published: (2025)

Sparsity greedoids and pebble game algorithms for posets
by: Lundqvist, Signe, et al.
Published: (2023)