Zobrazeno 1 - 10
of 2 854
pro vyhledávání: '"Wolff, Alexander."'
The crossing number of a graph is the least number of crossings over all drawings of the graph in the plane. Computing the crossing number of a given graph is NP-hard, but fixed-parameter tractable (FPT) with respect to the natural parameter. Two wel
Externí odkaz:
http://arxiv.org/abs/2412.04042
Autor:
Di Giacomo, Emilio, Didimo, Walter, Katsanou, Eleni, Schlipf, Lena, Symvonis, Antonios, Wolff, Alexander
Computing a Euclidean minimum spanning tree of a set of points is a seminal problem in computational geometry and geometric graph theory. We combine it with another classical problem in graph drawing, namely computing a monotone geometric representat
Externí odkaz:
http://arxiv.org/abs/2411.14038
Autor:
Angelini, Patrizio, Biedl, Therese, Chimani, Markus, Cornelsen, Sabine, Da Lozzo, Giordano, Hong, Seok-Hee, Liotta, Giuseppe, Patrignani, Maurizio, Pupyrev, Sergey, Rutter, Ignaz, Wolff, Alexander
Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward $k$-planar drawings of DAGs in which
Externí odkaz:
http://arxiv.org/abs/2409.01475
The treewidth is a structural parameter that measures the tree-likeness of a graph. Many algorithmic and combinatorial results are expressed in terms of the treewidth. In this paper, we study the treewidth of outer $k$-planar graphs, that is, graphs
Externí odkaz:
http://arxiv.org/abs/2408.04264
Autor:
Agrawal, Akanksha, Cabello, Sergio, Kaufmann, Michael, Saurabh, Saket, Sharma, Roohani, Uno, Yushi, Wolff, Alexander
Drawing a graph in the plane with as few crossings as possible is one of the central problems in graph drawing and computational geometry. Another option is to remove the smallest number of vertices or edges such that the remaining graph can be drawn
Externí odkaz:
http://arxiv.org/abs/2404.09771
Autor:
Blažej, Václav, Klemz, Boris, Klesen, Felix, Sieper, Marie Diana, Wolff, Alexander, Zink, Johannes
The problem Level Planarity asks for a crossing-free drawing of a graph in the plane such that vertices are placed at prescribed y-coordinates (called levels) and such that every edge is realized as a y-monotone curve. In the variant Constrained Leve
Externí odkaz:
http://arxiv.org/abs/2403.13702
Autor:
Firman, Oksana, Kindermann, Philipp, Klemz, Boris, Ravsky, Alexander, Wolff, Alexander, Zink, Johannes
We study the following combinatorial problem. Given a set of $n$ y-monotone \emph{wires}, a \emph{tangle} determines the order of the wires on a number of horizontal \emph{layers} such that the orders of the wires on any two consecutive layers differ
Externí odkaz:
http://arxiv.org/abs/2312.16213
Autor:
Firman, Oksana, Hegemann, Tim, Klemz, Boris, Klesen, Felix, Sieper, Marie Diana, Wolff, Alexander, Zink, Johannes
A crossing-free morph is a continuous deformation between two graph drawings that preserves straight-line pairwise noncrossing edges. Motivated by applications in 3D morphing problems, we initiate the study of morphing graph drawings in the plane in
Externí odkaz:
http://arxiv.org/abs/2311.14516