Marcus Schaefer

90 papers A* 4A 23B 4Misc 1Journal 54Unranked 3

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	Devil's Games and Qℝ: Continuous Games complete for the First-Order Theory of the Reals. CoRR Lucas Meijer, Arnaud de Mesmay, Tillmann Miltzow, Marcus Schaefer, Jack Stade
2025	J	`jnl`	How Hard is it to be a Star? Convex Geometry and the Real Hierarchy. CoRR Marcus Schaefer, Daniel Stefankovic
2025	J	`jnl`	Recognizing Penny and Marble Graphs is Hard for Existential Theory of the Reals. CoRR Anna Lubiw, Marcus Schaefer
2024	J	`jnl`	Beyond the Existential Theory of the Reals. Theory Comput. Syst. Marcus Schaefer, Daniel Stefankovic
2024	J	`jnl`	Spiraling and Folding: The Topological View. Discret. Comput. Geom. Jan Kyncl, Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic
2024	J	`jnl`	The Existential Theory of the Reals as a Complexity Class: A Compendium. CoRR Marcus Schaefer, Jean Cardinal, Tillmann Miltzow
2023	J	`jnl`	Hanani-Tutte for Radial Planarity II. Electron. J. Comb. Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer
2023	J	`jnl`	RAC-Drawability is ∃ℝ-complete and Related Results. J. Graph Algorithms Appl. Marcus Schaefer
2023	J	`jnl`	The Complexity of Angular Resolution. J. Graph Algorithms Appl. Marcus Schaefer
2022	J	`jnl`	Beyond the Existential Theory of the Reals. CoRR Marcus Schaefer, Daniel Stefankovic
2022	J	`jnl`	Hanani-Tutte and Hierarchical Partial Planarity. SIAM J. Discret. Math. Marcus Schaefer
2022	J	`jnl`	Spiraling and Folding: The Topological View. CoRR Jan Kyncl, Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic
2021	J	`jnl`	A New Algorithm for Embedding Plane Graphs at Fixed Vertex Locations. Electron. J. Comb. Marcus Schaefer
2021	J	`jnl`	Complexity of Geometric k-Planarity for Fixed k. J. Graph Algorithms Appl. Marcus Schaefer
2021	J	`jnl`	On the Complexity of Some Geometric Problems With Fixed Parameters. J. Graph Algorithms Appl. Marcus Schaefer
2021	A	`conf`	RAC-Drawability is ∃ ℝ-Complete. GD Marcus Schaefer
2021	J	`jnl`	RAC-drawability is ∃R-complete. CoRR Marcus Schaefer
2021	A*	`conf`	Strong Hanani-Tutte for the Torus. SoCG Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer
2021	J	`jnl`	Taking a Detour; or, Gioan's Theorem, and Pseudolinear Drawings of Complete Graphs. Discret. Comput. Geom. Marcus Schaefer
2020	J	`jnl`	Strong Hanani-Tutte for the Torus. CoRR Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer
2019	—	`ch.`	10 Reasons to Get Interested in Graph Drawing. Computing and Software Science Carla Binucci, Ulrik Brandes, Tim Dwyer, Martin Gronemann, Reinhard von Hanxleden, Marc J. van Kreveld, Petra Mutzel, Marcus Schaefer, Falk Schreiber, Bettina Speckmann
2019	J	`jnl`	A Proof of Levi's Extension Lemma. CoRR Marcus Schaefer
2019	J	`jnl`	Link Crossing Number is NP-hard. CoRR Arnaud de Mesmay, Marcus Schaefer, Eric Sedgwick
2018	J	`jnl`	The Complexity of Tensor Rank. Theory Comput. Syst. Marcus Schaefer, Daniel Stefankovic
2017	J	`jnl`	Fixed Points, Nash Equilibria, and the Existential Theory of the Reals. Theory Comput. Syst. Marcus Schaefer, Daniel Stefankovic
2017	J	`jnl`	Hanani-Tutte for Radial Planarity. J. Graph Algorithms Appl. Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer
2016	A	`conf`	Hanani-Tutte for Radial Planarity II. GD Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer
2016	J	`jnl`	Hanani-Tutte for Radial Planarity II. CoRR Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer
2016	J	`jnl`	Multi-sided Boundary Labeling. Algorithmica Philipp Kindermann, Benjamin Niedermann, Ignaz Rutter, Marcus Schaefer, André Schulz, Alexander Wolff
2016	J	`jnl`	The Complexity of Tensor Rank. CoRR Marcus Schaefer, Daniel Stefankovic
2015	J	`jnl`	Drawing Partially Embedded and Simultaneously Planar Graphs. J. Graph Algorithms Appl. Timothy M. Chan, Fabrizio Frati, Carsten Gutwenger, Anna Lubiw, Petra Mutzel, Marcus Schaefer
2015	A	`conf`	Hanani-Tutte for Radial Planarity. GD Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer
2015	A	`conf`	The Degenerate Crossing Number and Higher-Genus Embeddings. GD Marcus Schaefer, Daniel Stefankovic
2014	A	`conf`	A Crossing Lemma for the Pair-Crossing Number. GD Eyal Ackerman, Marcus Schaefer
2014	A	`conf`	Drawing Partially Embedded and Simultaneously Planar Graphs. GD Timothy M. Chan, Fabrizio Frati, Carsten Gutwenger, Anna Lubiw, Petra Mutzel, Marcus Schaefer
2014	J	`jnl`	Drawing Partially Embedded and Simultaneously Planar Graphs. CoRR Timothy M. Chan, Fabrizio Frati, Carsten Gutwenger, Anna Lubiw, Petra Mutzel, Marcus Schaefer
2014	A	`conf`	Picking Planar Edges; or, Drawing a Graph with a Planar Subgraph. GD Marcus Schaefer
2014	A	`conf`	Practical Experience with Hanani-Tutte for Testing c-Planarity. ALENEX Carsten Gutwenger, Petra Mutzel, Marcus Schaefer
2013	A	`conf`	Block Additivity of ℤ2-Embeddings. GD Marcus Schaefer, Daniel Stefankovic
2013	J	`jnl`	Multi-Sided Boundary Labeling CoRR Philipp Kindermann, Benjamin Niedermann, Ignaz Rutter, Marcus Schaefer, André Schulz, Alexander Wolff
2013	J	`jnl`	Picking Planar Edges; or, Drawing a Graph with a Planar Subgraph. CoRR Marcus Schaefer
2013	J	`jnl`	Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants. J. Graph Algorithms Appl. Marcus Schaefer
2013	B	`conf`	Two-Sided Boundary Labeling with Adjacent Sides. WADS Philipp Kindermann, Benjamin Niedermann, Ignaz Rutter, Marcus Schaefer, André Schulz, Alexander Wolff
2012	J	`jnl`	Adjacent Crossings Do Matter. J. Graph Algorithms Appl. Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic
2012	A	`conf`	Toward a Theory of Planarity: Hanani-Tutte and Planarity Variants. GD Marcus Schaefer
2011	A	`conf`	Adjacent Crossings Do Matter. GD Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic
2011	J	`jnl`	Crossing Numbers of Graphs with Rotation Systems. Algorithmica Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic
2011	B	`conf`	Hanani-Tutte and Monotone Drawings. WG Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic
2011	J	`jnl`	On the induced matching problem. J. Comput. Syst. Sci. Iyad A. Kanj, Michael J. Pelsmajer, Marcus Schaefer, Ge Xia
2011	J	`jnl`	Spiraling and Folding: The Word View. Algorithmica Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic
2010	J	`jnl`	Removing Independently Even Crossings. SIAM J. Discret. Math. Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic
2009	A	`conf`	Complexity of Some Geometric and Topological Problems. GD Marcus Schaefer
2009	A	`conf`	Removing Independently Even Crossings. GD Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic
2009	J	`jnl`	Removing even crossings on surfaces. Eur. J. Comb. Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic
2009	J	`jnl`	Strong Hanani--Tutte on the Projective Plane. SIAM J. Discret. Math. Michael J. Pelsmajer, Marcus Schaefer, Despina Stasi
2009	J	`jnl`	The complexity of nonrepetitive coloring. Discret. Appl. Math. Dániel Marx, Marcus Schaefer
2008	—	`conf`	Computing Dehn Twists and Geometric Intersection Numbers in Polynomial Time. CCCG Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic
2008	J	`jnl`	Odd Crossing Number and Crossing Number Are Not the Same. Discret. Comput. Geom. Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic
2008	A	`conf`	On the Induced Matching Problem. STACS Iyad A. Kanj, Michael J. Pelsmajer, Ge Xia, Marcus Schaefer
2007	A	`conf`	Crossing Number of Graphs with Rotation Systems. GD Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic
2007	A	`conf`	Crossing Numbers and Parameterized Complexity. GD Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic
2007	J	`jnl`	Folding and Spiralling: The Word View. Electron. Notes Discret. Math. Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic
2007	J	`jnl`	Removing Even Crossings on Surfaces. Electron. Notes Discret. Math. Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic
2007	J	`jnl`	Removing even crossings. J. Comb. Theory B Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic
2007	A	`conf`	Simultaneous Geometric Graph Embeddings. GD Alejandro Estrella-Balderrama, Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, Michael Schulz
2007	—	`conf`	Spiralling and Folding: The Topological View. CCCG Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic
2007	J	`jnl`	Train Tracks and Confluent Drawings. Algorithmica Peter Hui, Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic
2006	B	`conf`	Simultaneous Graph Embeddings with Fixed Edges. WG Elisabeth Gassner, Michael Jünger, Merijam Percan, Marcus Schaefer, Michael Schulz
2005	A	`conf`	Odd Crossing Number Is Not Crossing Number. GD Michael J. Pelsmajer, Marcus Schaefer, Daniel Stefankovic
2005	J	`jnl`	Solvability of Graph Inequalities. SIAM J. Discret. Math. Marcus Schaefer, Daniel Stefankovic
2004	J	`jnl`	Decidability of string graphs. J. Comput. Syst. Sci. Marcus Schaefer, Daniel Stefankovic
2004	B	`conf`	Paired Pointset Traversal. ISAAC Peter Hui, Marcus Schaefer
2004	—	`conf`	Parameterized Algorithms for Feedback Vertex Set. IWPEC Iyad A. Kanj, Michael J. Pelsmajer, Marcus Schaefer
2004	J	`jnl`	Simplicity and Strong Reductions Electron. Colloquium Comput. Complex. Marcus Schaefer, Stephen A. Fenner
2004	A	`conf`	Train Tracks and Confluent Drawings. GD Peter Hui, Marcus Schaefer, Daniel Stefankovic
2003	J	`jnl`	Induced Graph Ramsey Theory. Ars Comb. Marcus Schaefer, Pradyut Shah
2003	J	`jnl`	Recognizing string graphs in NP. J. Comput. Syst. Sci. Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic
2003	A	`conf`	Strong Reductions and Immunity for Exponential Time. STACS Marcus Schaefer, Frank Stephan
2002	Misc	`conf`	Algorithms for Normal Curves and Surfaces. COCOON Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic
2002	A*	`conf`	Recognizing string graphs in NP. STOC Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic
2001	A*	`conf`	Decidability of string graphs. STOC Marcus Schaefer, Daniel Stefankovic
2001	J	`jnl`	Graph Ramsey Theory and the Polynomial Hierarchy. J. Comput. Syst. Sci. Marcus Schaefer
2001	J	`jnl`	Hyper-polynomial hierarchies and the polynomial jump. Theor. Comput. Sci. Stephen A. Fenner, Steven Homer, Randall J. Pruim, Marcus Schaefer
2000	A	`conf`	Deciding the K-Dimension is PSPACE-Complete. CCC Marcus Schaefer
1999	J	`jnl`	Bounded Immunity and Btt-Reductions. Math. Log. Q. Stephen A. Fenner, Marcus Schaefer
1999	J	`jnl`	Deciding the Vapnik-Červonenkis Dimension in ∑ J. Comput. Syst. Sci. Marcus Schaefer
1999	A	`conf`	Graph Ramsey Theory and the Polynomial Hierarchy (Abstract). CCC Marcus Schaefer
1999	A*	`conf`	Graph Ramsey Theory and the Polynomial Hierarchy. STOC Marcus Schaefer
1998	J	`jnl`	A guided tour of minimal indices and shortest descriptions. Arch. Math. Log. Marcus Schaefer
1997	A	`conf`	Hyper-Polynomial Hierarchies and the NP-Jump. CCC Stephen A. Fenner, Steven Homer, Randall J. Pruim, Marcus Schaefer