Marcus Schaefer

Affiliations:
  • DePaul University, School of Computing, Chicago, IL, USA


According to our database1, Marcus Schaefer authored at least 64 papers between 1995 and 2022.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2022
The Degenerate Crossing Number and Higher-Genus Embeddings.
J. Graph Algorithms Appl., 2022

2021
On the Complexity of Some Geometric Problems With Fixed Parameters.
J. Graph Algorithms Appl., 2021

Complexity of Geometric k-Planarity for Fixed k.
J. Graph Algorithms Appl., 2021

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

A New Algorithm for Embedding Plane Graphs at Fixed Vertex Locations.
Electron. J. Comb., 2021

RAC-Drawability is ∃ ℝ-Complete.
Proceedings of the Graph Drawing and Network Visualization, 2021

Strong Hanani-Tutte for the Torus.
Proceedings of the 37th International Symposium on Computational Geometry, 2021

2019
10 Reasons to Get Interested in Graph Drawing.
Proceedings of the Computing and Software Science - State of the Art and Perspectives, 2019

A Proof of Levi's Extension Lemma.
CoRR, 2019

Link Crossing Number is NP-hard.
CoRR, 2019

2018
The Complexity of Tensor Rank.
Theory Comput. Syst., 2018

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

Hanani-Tutte for Radial Planarity.
J. Graph Algorithms Appl., 2017

2016
Multi-sided Boundary Labeling.
Algorithmica, 2016

Hanani-Tutte for Radial Planarity II.
Proceedings of the Graph Drawing and Network Visualization, 2016

2015
Drawing Partially Embedded and Simultaneously Planar Graphs.
J. Graph Algorithms Appl., 2015

2014
Picking Planar Edges; or, Drawing a Graph with a Planar Subgraph.
Proceedings of the Graph Drawing - 22nd International Symposium, GD 2014, Würzburg, 2014

A Crossing Lemma for the Pair-Crossing Number.
Proceedings of the Graph Drawing - 22nd International Symposium, GD 2014, Würzburg, 2014

Practical Experience with Hanani-Tutte for Testing c-Planarity.
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.
J. Graph Algorithms Appl., 2013

Two-Sided Boundary Labeling with Adjacent Sides.
Proceedings of the Algorithms and Data Structures - 13th International Symposium, 2013

Block Additivity of ℤ2-Embeddings.
Proceedings of the Graph Drawing - 21st International Symposium, 2013

2012
Adjacent Crossings Do Matter.
J. Graph Algorithms Appl., 2012

2011
On the induced matching problem.
J. Comput. Syst. Sci., 2011

Spiraling and Folding: The Word View.
Algorithmica, 2011

Crossing Numbers of Graphs with Rotation Systems.
Algorithmica, 2011

Hanani-Tutte and Monotone Drawings.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011

2010
Removing Independently Even Crossings.
SIAM J. Discret. Math., 2010

2009
Strong Hanani--Tutte on the Projective Plane.
SIAM J. Discret. Math., 2009

The complexity of nonrepetitive coloring.
Discret. Appl. Math., 2009

Complexity of Some Geometric and Topological Problems.
Proceedings of the Graph Drawing, 17th International Symposium, 2009

2008
Odd Crossing Number and Crossing Number Are Not the Same.
Discret. Comput. Geom., 2008

Computing Dehn Twists and Geometric Intersection Numbers in Polynomial Time.
Proceedings of the 20th Annual Canadian Conference on Computational Geometry, 2008

2007
Cuppability of Simple and Hypersimple Sets.
Notre Dame J. Formal Log., 2007

Removing even crossings.
J. Comb. Theory, Ser. B, 2007

Folding and Spiralling: The Word View.
Electron. Notes Discret. Math., 2007

Removing Even Crossings on Surfaces.
Electron. Notes Discret. Math., 2007

Train Tracks and Confluent Drawings.
Algorithmica, 2007

Crossing Numbers and Parameterized Complexity.
Proceedings of the Graph Drawing, 15th International Symposium, 2007

Crossing Number of Graphs with Rotation Systems.
Proceedings of the Graph Drawing, 15th International Symposium, 2007

Simultaneous Geometric Graph Embeddings.
Proceedings of the Graph Drawing, 15th International Symposium, 2007

Spiralling and Folding: The Topological View.
Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007

2006
Simultaneous Graph Embeddings with Fixed Edges.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2006

2005
Solvability of Graph Inequalities.
SIAM J. Discret. Math., 2005

Odd Crossing Number Is Not Crossing Number.
Proceedings of the Graph Drawing, 13th International Symposium, 2005

2004
Decidability of string graphs.
J. Comput. Syst. Sci., 2004

Simplicity and Strong Reductions
Electron. Colloquium Comput. Complex., 2004

Parameterized Algorithms for Feedback Vertex Set.
Proceedings of the Parameterized and Exact Computation, First International Workshop, 2004

Paired Pointset Traversal.
Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

Train Tracks and Confluent Drawings.
Proceedings of the Graph Drawing, 12th International Symposium, 2004

2003
Recognizing string graphs in NP.
J. Comput. Syst. Sci., 2003

Induced Graph Ramsey Theory.
Ars Comb., 2003

Strong Reductions and Immunity for Exponential Time.
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.
Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002

2001
Hyper-polynomial hierarchies and the polynomial jump.
Theor. Comput. Sci., 2001

Graph Ramsey Theory and the Polynomial Hierarchy.
J. Comput. Syst. Sci., 2001

2000
Deciding the K-Dimension is PSPACE-Complete.
Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999
Bounded Immunity and Btt-Reductions.
Math. Log. Q., 1999

Deciding the Vapnik-Červonenkis Dimension in ∑<sup>p</sup><sub>3</sub>-Complete.
J. Comput. Syst. Sci., 1999

Graph Ramsey Theory and the Polynomial Hierarchy (Abstract).
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
A guided tour of minimal indices and shortest descriptions.
Arch. Math. Log., 1998

1997
Hyper-Polynomial Hierarchies and the NP-Jump.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996
Deciding the Vapnik-Cervonenkis dimension is Sigma<sup>P</sup><sub>3</sub>-complete.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995
Computability of Convex Sets (Extended Abstract).
Proceedings of the STACS 95, 1995


  Loading...