Imagen de Portada

Improving the Crossing Lemma by Characterizing Dense 2-Planar and 3-Planar Graphs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Büngener, Aaron, Kaufmann, Michael
Formato:	Preprint
Publicado:	2024
Materias:	Combinatorics Discrete Mathematics G.2.2; F.2.2
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

New Results on Edge-coloring and Total-coloring of Split Graphs
por: Couto, Fernanda, et al.
Publicado: (2023)

A Tight Lower Bound on Cubic Vertices and Upper Bounds on Thin and Non-thin edges in Planar Braces
por: De, Koustav
Publicado: (2025)

A first view on the density of 5-planar graphs
por: Büngener, Aaron, et al.
Publicado: (2025)

On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
por: MacRury, Calum, et al.
Publicado: (2022)

On Minimum Maximal Distance-k Matchings
por: Kartynnik, Yury, et al.
Publicado: (2016)

Online Matching and Contention Resolution for Edge Arrivals with Vanishing Probabilities
por: Ma, Will, et al.
Publicado: (2024)

On λ-backbone coloring of cliques with tree backbones in linear time
por: Michalik, Krzysztof, et al.
Publicado: (2021)

Online Bipartite Matching in the Probe-Commit Model
por: Borodin, Allan, et al.
Publicado: (2023)

On the Uncrossed Number of Graphs
por: Balko, Martin, et al.
Publicado: (2024)

An Upper Bound for the Double Domination Number in Maximal Outerplanar Graphs
por: Araki, Toru
Publicado: (2026)

Monotonicity of the cops and robber game for bounded depth treewidth
por: Adler, Isolde, et al.
Publicado: (2024)

Revisiting classical results on kernels in digraphs
por: Langlois, Hélène, et al.
Publicado: (2025)

Binary Stretch Embedding of Weighted Graphs
por: Ebrahimi, Javad B., et al.
Publicado: (2024)

Minimizing an Uncrossed Collection of Drawings
por: Hliněný, Petr, et al.
Publicado: (2023)

General Strong Bound on the Uncrossed Number via a Tight Bound for the Maximum Uncrossed Subgraph Number
por: Charvy, Gaspard, et al.
Publicado: (2025)

Closed form logical error rate approximations for surface codes
por: Regev, Shaked, et al.
Publicado: (2026)

The Density Formula: One Lemma to Bound Them All
por: Kaufmann, Michael, et al.
Publicado: (2023)

Optimal covering of rectangular grid graphs with tours of constrained length
por: Bereg, Sergey, et al.
Publicado: (2025)

An O(log n)-Approximation Algorithm for (p,q)-Flexible Graph Connectivity via Independent Rounding
por: Ibrahimpur, Sharat, et al.
Publicado: (2025)

Breaking the Symmetries of Amenable Graphs
por: Cheng, Christine T.
Publicado: (2025)

Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
por: Anand, Emile
Publicado: (2025)

On Strict Brambles
por: Lardas, Emmanouil, et al.
Publicado: (2022)

Treewidth is Polynomial in Maximum Degree on Weakly Sparse Graphs Excluding a Planar Induced Minor
por: Bonnet, Édouard, et al.
Publicado: (2023)

Complexity of Firefighting on Graphs
por: Althoetmar, Julius, et al.
Publicado: (2025)

Compact Representation of Semilinear and Terrain-like Graphs
por: Cardinal, Jean, et al.
Publicado: (2025)

Independent Set Enumeration in King Graphs by Tensor Network Contractions
por: Liang, Kai
Publicado: (2025)

Enumeration of Polyominoes up to Size N=59
por: Shirakawa, Toshihiro
Publicado: (2025)

The steady-states of splitter networks
por: Couëtoux, Basile, et al.
Publicado: (2024)

Deterministic Minimum Steiner Cut in Maximum Flow Time
por: Ding, Matthew, et al.
Publicado: (2023)

Highly Connected Steiner Subgraph -- Parameterized Algorithms and Applications to Hitting Set Problems
por: Eiben, Eduard, et al.
Publicado: (2023)

Forward-backward Contention Resolution Schemes for Fair Rationing
por: Ma, Will, et al.
Publicado: (2025)

A polynomial-time algorithm for recognizing high-bandwidth graphs
por: Varona, Luis M. B.
Publicado: (2026)

Interval Graphs are Reconstructible
por: Heinrich, Irene, et al.
Publicado: (2025)

Random Embeddings of Graphs: The Expected Number of Faces in Most Graphs is Logarithmic
por: Loth, Jesse Campion, et al.
Publicado: (2022)

Algorithmic Applications of Tyshkevich's Graph Decomposition: A Primer and a Toolkit
por: Cheng, Christine T., et al.
Publicado: (2026)

Flipping odd matchings in geometric and combinatorial settings
por: Aichholzer, Oswin, et al.
Publicado: (2025)

Some Thoughts on Graph Similarity
por: Grohe, Martin
Publicado: (2024)

Optimal Path Partitions in Subcubic and Almost-subcubic Graphs
por: Masařík, Tomáš, et al.
Publicado: (2026)

Open Packing in Graphs: Bounds and Complexity
por: Shalu, M. A., et al.
Publicado: (2024)

Every Graph is Essential to Large Treewidth
por: Alecu, Bogdan, et al.
Publicado: (2025)