Marcus Schaefer

Theory Comput. Syst., April, 2024

The Existential Theory of the Reals as a Complexity Class: A Compendium.

[BibT_eX]

[DOI]

Jean Cardinal

Tillmann Miltzow

CoRR, 2024

2023

RAC-Drawability is ∃ℝ-complete and Related Results.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2023

The Complexity of Angular Resolution.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2023

Hanani-Tutte for Radial Planarity II.

[BibT_eX]

[DOI]

Radoslav Fulek

Electron. J. Comb., 2023

2022

Hanani-Tutte and Hierarchical Partial Planarity.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., December, 2022

The Degenerate Crossing Number and Higher-Genus Embeddings.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2022

2021

On the Complexity of Some Geometric Problems With Fixed Parameters.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2021

Complexity of Geometric k-Planarity for Fixed k.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2021

Taking a Detour; or, Gioan's Theorem, and Pseudolinear Drawings of Complete Graphs.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2021

A New Algorithm for Embedding Plane Graphs at Fixed Vertex Locations.

[BibT_eX]

[DOI]

Electron. J. Comb., 2021

RAC-Drawability is ∃ ℝ-Complete.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing and Network Visualization - 29th International Symposium, 2021

Strong Hanani-Tutte for the Torus.

[BibT_eX]

[DOI]

Radoslav Fulek

Proceedings of the 37th International Symposium on Computational Geometry, 2021

2019

10 Reasons to Get Interested in Graph Drawing.

[BibT_eX]

[DOI]

Reinhard von Hanxleden

Proceedings of the Computing and Software Science - State of the Art and Perspectives, 2019

A Proof of Levi's Extension Lemma.

[BibT_eX]

[DOI]

CoRR, 2019

Link Crossing Number is NP-hard.

[BibT_eX]

[DOI]

Arnaud de Mesmay

CoRR, 2019

2018

The Complexity of Tensor Rank.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2018

2017

Fixed Points, Nash Equilibria, and the Existential Theory of the Reals.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

Hanani-Tutte for Radial Planarity.

[BibT_eX]

[DOI]

Radoslav Fulek

J. Graph Algorithms Appl., 2017

2016

Multi-sided Boundary Labeling.

[BibT_eX]

[DOI]

Algorithmica, 2016

2015

Drawing Partially Embedded and Simultaneously Planar Graphs.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2015

2014

Picking Planar Edges; or, Drawing a Graph with a Planar Subgraph.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing - 22nd International Symposium, 2014

A Crossing Lemma for the Pair-Crossing Number.

[BibT_eX]

[DOI]

Eyal Ackerman

Proceedings of the Graph Drawing - 22nd International Symposium, 2014

Practical Experience with Hanani-Tutte for Testing c-Planarity.

[BibT_eX]

[DOI]

Carsten Gutwenger

Petra Mutzel

Proceedings of the 2014 Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments, 2014

2013

Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2013

Two-Sided Boundary Labeling with Adjacent Sides.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

Block Additivity of ℤ2-Embeddings.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing - 21st International Symposium, 2013

2012

Adjacent Crossings Do Matter.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2012

2011

On the induced matching problem.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

Spiraling and Folding: The Word View.

[BibT_eX]

[DOI]

Algorithmica, 2011

Crossing Numbers of Graphs with Rotation Systems.

[BibT_eX]

[DOI]

Algorithmica, 2011

Hanani-Tutte and Monotone Drawings.

[BibT_eX]

[DOI]

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

2010

Removing Independently Even Crossings.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2010

2009

Strong Hanani--Tutte on the Projective Plane.

[BibT_eX]

[DOI]

Despina Stasi

SIAM J. Discret. Math., 2009

The complexity of nonrepetitive coloring.

[BibT_eX]

[DOI]

Dániel Marx

Discret. Appl. Math., 2009

Complexity of Some Geometric and Topological Problems.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing, 17th International Symposium, 2009

2008

Odd Crossing Number and Crossing Number Are Not the Same.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2008

Computing Dehn Twists and Geometric Intersection Numbers in Polynomial Time.

[BibT_eX]

Proceedings of the 20th Annual Canadian Conference on Computational Geometry, 2008

2007

Cuppability of Simple and Hypersimple Sets.

[BibT_eX]

[DOI]

Martin Kummer

Notre Dame J. Formal Log., 2007

Removing even crossings.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2007

Folding and Spiralling: The Word View.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2007

Removing Even Crossings on Surfaces.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2007

Train Tracks and Confluent Drawings.

[BibT_eX]

[DOI]

Algorithmica, 2007

Crossing Numbers and Parameterized Complexity.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing, 15th International Symposium, 2007

Crossing Number of Graphs with Rotation Systems.

[BibT_eX]

[DOI]

Alejandro Estrella-Balderrama

Proceedings of the Graph Drawing, 15th International Symposium, 2007

Simultaneous Geometric Graph Embeddings.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing, 15th International Symposium, 2007

Spiralling and Folding: The Topological View.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007

2006

Simultaneous Graph Embeddings with Fixed Edges.

[BibT_eX]

[DOI]

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

2005

Solvability of Graph Inequalities.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2005

Odd Crossing Number Is Not Crossing Number.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing, 13th International Symposium, 2005

2004

Decidability of string graphs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2004

Simplicity and Strong Reductions

[BibT_eX]

[DOI]

Stephen A. Fenner

Electron. Colloquium Comput. Complex., 2004

Parameterized Algorithms for Feedback Vertex Set.

[BibT_eX]

[DOI]

Iyad A. Kanj

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

Paired Pointset Traversal.

[BibT_eX]

[DOI]

Peter Hui

Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

Train Tracks and Confluent Drawings.

[BibT_eX]

[DOI]

Peter Hui

Proceedings of the Graph Drawing, 12th International Symposium, 2004

2003

Recognizing string graphs in NP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2003

Induced Graph Ramsey Theory.

[BibT_eX]

Pradyut Shah

Ars Comb., 2003

Strong Reductions and Immunity for Exponential Time.

[BibT_eX]

[DOI]

Frank Stephan

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

2002

Algorithms for Normal Curves and Surfaces.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002

2001

Hyper-polynomial hierarchies and the polynomial jump.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

Graph Ramsey Theory and the Polynomial Hierarchy.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

2000

Deciding the K-Dimension is PSPACE-Complete.

[BibT_eX]

[DOI]

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999

Bounded Immunity and Btt-Reductions.

[BibT_eX]

[DOI]

Stephen A. Fenner

Math. Log. Q., 1999

Deciding the Vapnik-Červonenkis Dimension in ∑p3-Complete.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1999

Graph Ramsey Theory and the Polynomial Hierarchy (Abstract).

[BibT_eX]

[DOI]

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

A guided tour of minimal indices and shortest descriptions.

[BibT_eX]

[DOI]

Arch. Math. Log., 1998

1997

Hyper-Polynomial Hierarchies and the NP-Jump.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

Deciding the Vapnik-Cervonenkis dimension is SigmaP3-complete.

[BibT_eX]

[DOI]

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995

Computability of Convex Sets (Extended Abstract).

[BibT_eX]

[DOI]

Martin Kummer