Petr Hlinený

CoRR, June, 2025

Stack and queue numbers of graphs revisited.

[BibT_eX]

[DOI]

Adam Straka

Eur. J. Comb., 2025

Twin-width of planar graphs; a short proof.

[BibT_eX]

[DOI]

Eur. J. Comb., 2025

On 13-crossing-critical graphs with arbitrarily large degrees.

[BibT_eX]

[DOI]

Michal Korbela

Discret. Math., 2025

Complexity of Anchored Crossing Number and Crossing Number of Almost Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

Transductions of Graph Classes Admitting Product Structure.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM/IEEE Symposium on Logic in Computer Science, 2025

A Unified FPT Framework for Crossing Number Problems.

[BibT_eX]

[DOI]

Éric Colin de Verdière

Proceedings of the 33rd Annual European Symposium on Algorithms, 2025

2024

FPT Algorithms for Crossing Number Problems: A Unified Approach.

[BibT_eX]

[DOI]

Éric Colin de Verdière

CoRR, 2024

Note on Min-k-Planar Drawings of Graphs.

[BibT_eX]

[DOI]

CoRR, 2024

ℋ-Clique-Width and a Hereditary Analogue of Product Structure.

[BibT_eX]

[DOI]

Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science, 2024

Crossing Number Is NP-Hard for Constant Path-Width (And Tree-Width).

[BibT_eX]

[DOI]

Liana Khazaliya

Proceedings of the 35th International Symposium on Algorithms and Computation, 2024

Note on Min- k-Planar Drawings of Graphs.

[BibT_eX]

[DOI]

Csenge Lili Ködmön

Proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization, 2024

On the Uncrossed Number of Graphs.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization, 2024

2023

Efficient Isomorphism for Sd-Graphs and T-Graphs.

[BibT_eX]

[DOI]

Algorithmica, February, 2023

Recognizing H-Graphs - Beyond Circular-Arc Graphs.

[BibT_eX]

[DOI]

Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science, 2023

Sparse Graphs of Twin-Width 2 Have Bounded Tree-Width.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

Twin-Width of Planar Graphs Is at Most 8, and at Most 6 When Bipartite Planar.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Minimizing an Uncrossed Collection of Drawings.

[BibT_eX]

[DOI]

Tomás Masarík

Proceedings of the Graph Drawing and Network Visualization - 31st International Symposium, 2023

2022

Beyond circular-arc graphs - recognizing lollipop graphs and medusa graphs.

[BibT_eX]

[DOI]

CoRR, 2022

Twin-width of Planar Graphs is at most 8.

[BibT_eX]

[DOI]

CoRR, 2022

Twin-width and Limits of Tractability of FO Model Checking on Geometric Graphs.

[BibT_eX]

[DOI]

Filip Pokrývka

CoRR, 2022

Automorphism Group of Marked Interval Graphs in FPT.

[BibT_eX]

[DOI]

Deniz Agaoglu

CoRR, 2022

Twin-Width and Transductions of Proper k-Mixed-Thin Graphs.

[BibT_eX]

[DOI]

Jakub Balabán

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2022

Isomorphism Testing for T-graphs in FPT.

[BibT_eX]

[DOI]

Proceedings of the WALCOM: Algorithms and Computation, 2022

Graph Product Structure for h-Framed Graphs.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

Parameterised Partially-Predrawn Crossing Number.

[BibT_eX]

[DOI]

Thekla Hamm

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges.

[BibT_eX]

[DOI]

CoRR, 2021

Computational Complexity of Covering Multigraphs with Semi-Edges: Small Cases.

[BibT_eX]

[DOI]

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

Twin-Width Is Linear in the Poset Width.

[BibT_eX]

[DOI]

Jakub Balabán

Proceedings of the 16th International Symposium on Parameterized and Exact Computation, 2021

2020

Toroidal grid minors and stretch in embedded graphs.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2020

Clique-Width of Point Configurations.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2020

Isomorphism Problem for S_d-Graphs.

[BibT_eX]

[DOI]

Deniz Agaoglu

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

2019

Shrub-depth: Capturing Height of Dense Graphs.

[BibT_eX]

[DOI]

Patrice Ossona de Mendez

Log. Methods Comput. Sci., 2019

Bounded maximum degree conjecture holds precisely for c-crossing-critical graphs with c≤12.

[BibT_eX]

[DOI]

CoRR, 2019

Exact Crossing Number Parameterized by Vertex Cover.

[BibT_eX]

[DOI]

Abhisekh Sankaran

Proceedings of the Graph Drawing and Network Visualization - 27th International Symposium, 2019

Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c <= 12.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Computational Geometry, 2019

On Conflict-Free Chromatic Guarding of Simple Polygons.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization and Applications, 2019

2018

Deciding Parity of Graph Crossing Number.

[BibT_eX]

[DOI]

Carsten Thomassen

SIAM J. Discret. Math., 2018

A Simpler Self-reduction Algorithm for Matroid Path-Width.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2018

Parameterized extension complexity of independent set and related problems.

[BibT_eX]

[DOI]

Jakub Gajarský

Hans Raj Tiwary

Discret. Appl. Math., 2018

Structure and Generation of Crossing-Critical Graphs.

[BibT_eX]

[DOI]

Zdenek Dvorák

Bojan Mohar

Proceedings of the 34th International Symposium on Computational Geometry, 2018

2017

First order limits of sparse graphs: Plane trees and path-width.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2017

FO Model Checking of Geometric Graphs.

[BibT_eX]

[DOI]

Filip Pokrývka

Bodhayan Roy

Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

On Colourability of Polygon Visibility Graphs.

[BibT_eX]

[DOI]

Onur Cagirici

Bodhayan Roy

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

Parameterized Shifted Combinatorial Optimization.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 23rd International Conference, 2017

2016

Tree-depth and vertex-minors.

[BibT_eX]

[DOI]

Eur. J. Comb., 2016

A New Perspective on FO Model Checking of Dense Graph Classes.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 2016

Crossing Number is Hard for Kernelization.

[BibT_eX]

[DOI]

Marek Dernár

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

Inserting Multiple Edges into a Planar Graph.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015

Planar emulators conjecture is nearly true for cubic graphs.

[BibT_eX]

[DOI]

Martin Derka

Eur. J. Comb., 2015

Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences.

[BibT_eX]

[DOI]

Jakub Gajarský

Log. Methods Comput. Sci., 2015

Strategy Synthesis in Adversarial Patrolling Games.

[BibT_eX]

[DOI]

CoRR, 2015

Practical Exhaustive Generation of Small Multiway Cuts in Sparse Graphs.

[BibT_eX]

[DOI]

Ondrej Slámecka

Proceedings of the Mathematical and Engineering Methods in Computer Science, 2015

On Hardness of the Joint Crossing Number.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 26th International Symposium, 2015

On Degree Properties of Crossing-Critical Families of Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing and Network Visualization - 23rd International Symposium, 2015

FO Model Checking on Posets of Bounded Width.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Computing the Stretch of an Embedded Graph.

[BibT_eX]

[DOI]

Sergio Cabello

SIAM J. Discret. Math., 2014

Lower bounds on the complexity of MSO1 model-checking.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2014

Faster Existential FO Model Checking on Posets.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 25th International Symposium, 2014

2013

A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width.

[BibT_eX]

[DOI]

Fernando Sánchez Villaamil

Jan Obdrzálek

Eur. J. Comb., 2013

FO Model Checking of Interval Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

Kernelization Using Structural Parameters on Sparse Graph Classes.

[BibT_eX]

[DOI]

Somnath Sikdar

Proceedings of the Algorithms - ESA 2013, 2013

2012

Preface.

[BibT_eX]

[DOI]

Antonín Kucera

Theor. Comput. Sci., 2012

Vertex insertion approximates the crossing number of apex graphs.

[BibT_eX]

[DOI]

Petra Mutzel

Eur. J. Comb., 2012

Detours in Scope-Based Route Planning

[BibT_eX]

[DOI]

CoRR, 2012

Dynamic Scope-Based Dijkstra's Algorithm

[BibT_eX]

[DOI]

CoRR, 2012

Generalized Maneuvers in Route Planning for Computing and Informatics.

[BibT_eX]

[DOI]

Comput. Informatics, 2012

Lower Bounds on the Complexity of MSO_1 Model-Checking.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

When Trees Grow Low: Shrubs and Fast MSO1.

[BibT_eX]

[DOI]

Patrice Ossona de Mendez

Reshma Ramadurai

Proceedings of the Mathematical Foundations of Computer Science 2012, 2012

Faster Deciding MSO Properties of Trees of Fixed Height, and Some Consequences.

[BibT_eX]

[DOI]

Jakub Gajarský

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011

Parameterized Problems Related to Seidel's Switching.

[BibT_eX]

[DOI]

Discret. Math. Theor. Comput. Sci., 2011

Lower Bounds on the Complexity of MSO1 Model-Checking

[BibT_eX]

[DOI]

CoRR, 2011

Multi-Stage Improved Route Planning Approach: theoretical foundations

[BibT_eX]

[DOI]

CoRR, 2011

Clique-width: When Hard Does Not Mean Impossible.

[BibT_eX]

[DOI]

Jan Obdrzálek

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Generalized Maneuvers in Route Planning.

[BibT_eX]

[DOI]

Proceedings of the Mathematical and Engineering Methods in Computer Science, 2011

How Not to Characterize Planar-Emulable Graphs.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 22nd International Workshop, 2011

A Tighter Insertion-Based Approximation of the Crossing Number.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Scope-Based Route Planning.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2011, 2011

2010

20 Years of Negami's Planar Cover Conjecture.

[BibT_eX]

[DOI]

Graphs Comb., 2010

On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2010

New Results on the Complexity of Oriented Colouring on Restricted Digraph Classes.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2010: Theory and Practice of Computer Science, 2010

Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Are There Any Good Digraph Width Measures?

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation - 5th International Symposium, 2010

Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width.

[BibT_eX]

[DOI]

Jan Obdrzálek

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

2009

Addendum to matroid tree-width.

[BibT_eX]

[DOI]

Geoff Whittle

Eur. J. Comb., 2009

Preface -- Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09).

[BibT_eX]

[DOI]

Václav Matyás

Tomás Vojnar

Proceedings of the Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, 2009

On Digraph Width Measures in Parameterized Algorithmics.

[BibT_eX]

[DOI]

Proceedings of the Parameterized and Exact Computation, 4th International Workshop, 2009

Better Polynomial Algorithms on Graphs of Bounded Rank-Width.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms, 20th International Workshop, 2009

2008

Stars and Bonds in Crossing-Critical Graphs.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2008

New Infinite Families of Almost-Planar Crossing-Critical Graphs.

[BibT_eX]

[DOI]

Electron. J. Comb., 2008

Width Parameters Beyond Tree-width and their Applications.

[BibT_eX]

[DOI]

Comput. J., 2008

Automata approach to graphs of bounded rank-width.

[BibT_eX]

Proceedings of the 19th International Workshop on Combinatorial Algorithms, 2008

Approximating the Crossing Number of Apex Graphs.

[BibT_eX]

[DOI]

Petra Mutzel

Proceedings of the Graph Drawing, 16th International Symposium, 2008

2007

Some Hard Problems on Matroid Spikes.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2007

Preface.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2007

The crossing number of a projective graph is quadratic in the face-width.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2007

Approximating the Crossing Number of Toroidal Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

Finding Branch-Decompositions and Rank-Decompositions.

[BibT_eX]

[DOI]

Sang-il Oum

Proceedings of the Algorithms, 2007

2006

Trees, grids, and MSO decidability: From graphs to matroids.

[BibT_eX]

[DOI]

Detlef Seese

Theor. Comput. Sci., 2006

Matroid tree-width.

[BibT_eX]

[DOI]

Geoff Whittle

Eur. J. Comb., 2006

Equivalence-free exhaustive generation of matroid representations.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2006

The Tutte Polynomial for Matroids of Bounded Branch-Width.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2006

Balanced Signings and the Chromatic Number of Oriented Matroids.

[BibT_eX]

[DOI]

Luis A. Goddyn

Winfried Hochstättler

Comb. Probab. Comput., 2006

On Matroid Representability and Minor Problems.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

On the Crossing Number of Almost Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing, 14th International Symposium, 2006

2005

A Parametrized Algorithm for Matroid Branch-Width.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Computing the Tutte Polynomial on Graphs of Bounded Clique-Width.

[BibT_eX]

[DOI]

Omer Giménez

Marc Noy

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2005

2004

Bridging Separations in Matroids.

[BibT_eX]

[DOI]

James F. Geelen

Geoffrey P. Whittle

SIAM J. Discret. Math., 2004

On possible counterexamples to Negami's planar cover conjecture.

[BibT_eX]

[DOI]

Robin Thomas

J. Graph Theory, 2004

Crossing Number Is Hard for Cubic Graphs.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

On Decidability of MSO Theories of Representable Matroids.

[BibT_eX]

[DOI]

Detlef Seese

Proceedings of the Parameterized and Exact Computation, First International Workshop, 2004

2003

Crossing-number critical graphs have bounded path-width.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2003

Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids.

[BibT_eX]

[DOI]

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

On Matroid Properties Definable in the MSO Logic.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

2002

On the Excluded Minors for Matroids of Branch-Width Three.

[BibT_eX]

[DOI]

Electron. J. Comb., 2002

2001

Another two graphs with no planar covers.

[BibT_eX]

[DOI]

J. Graph Theory, 2001

Representing graphs by disks and balls (a survey of recognition-complexity results).

[BibT_eX]

[DOI]

Jan Kratochvíl

Discret. Math., 2001

Contact graphs of line segments are NP-complete.

[BibT_eX]

[DOI]

Discret. Math., 2001

An Addition to Art Galleries with Interior Walls.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2001

Crossing-Critical Graphs and Path-Width.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing, 9th International Symposium, 2001

1999

A note on possible extensions of Negami's conjecture.

[BibT_eX]

[DOI]

J. Graph Theory, 1999

1998

Classes and Recognition of Curve Contact Graphs, .

[BibT_eX]

[DOI]

J. Comb. Theory B, 1998

The Maximal Clique and Colourability of Curve Contact Graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 1998

1997

Computational Complexity of the Krausz Dimension of Graphs.

[BibT_eX]

[DOI]

Jan Kratochvíl

Proceedings of the Graph-Theoretic Concepts in Computer Science, 1997

Touching Graphs of Unit Balls.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing, 5th International Symposium, 1997

1995

Contact Graphs of Curves.

[BibT_eX]

[DOI]