Zobrazeno 1 - 10
of 214
pro vyhledávání: '"Chaplick, Steven"'
Phylogenetic trees are leaf-labelled trees used to model the evolution of species. In practice it is not uncommon to obtain two topologically distinct trees for the same set of species, and this motivates the use of distance measures to quantify diss
Externí odkaz:
http://arxiv.org/abs/2409.18634
We show that every planar graph has a monotone topological 2-page book embedding where at most (4n-10)/5 (of potentially 3n-6) edges cross the spine, and every edge crosses the spine at most once; such an edge is called a biarc. We can also guarantee
Externí odkaz:
http://arxiv.org/abs/2408.14299
In this article we prove that the minimum-degree greedy algorithm, with adversarial tie-breaking, is a $(2/3)$-approximation for the Maximum Independent Set problem on interval graphs. We show that this is tight, even on unit interval graphs of maxim
Externí odkaz:
http://arxiv.org/abs/2403.10868
Autor:
Martinez, Virginia Aardevol, Chaplick, Steven, Kelk, Steven, Meuwese, Ruben, Mihalak, Matus, Stamoulis, Georgios
There are multiple factors which can cause the phylogenetic inference process to produce two or more conflicting hypotheses of the evolutionary history of a set X of biological entities. That is: phylogenetic trees with the same set of leaf labels X
Externí odkaz:
http://arxiv.org/abs/2309.01110
Let $G$ be an undirected graph. We say that $G$ contains a ladder of length $k$ if the $2 \times (k+1)$ grid graph is an induced subgraph of $G$ that is only connected to the rest of $G$ via its four cornerpoints. We prove that if all the ladders con
Externí odkaz:
http://arxiv.org/abs/2302.10662
Autor:
Chaplick, Steven, Di Giacomo, Emilio, Frati, Fabrizio, Ganian, Robert, Raftopoulou, Chrysanthi N., Simonov, Kirill
We present an $O(n^2)$-time algorithm to test whether an $n$-vertex directed partial $2$-tree is upward planar. This result improves upon the previously best known algorithm, which runs in $O(n^4)$ time.
Comment: Appears in the Proceedings of th
Comment: Appears in the Proceedings of th
Externí odkaz:
http://arxiv.org/abs/2208.12548
Autor:
Balko, Martin, Chaplick, Steven, Ganian, Robert, Gupta, Siddharth, Hoffmann, Michael, Valtr, Pavel, Wolff, Alexander
An obstacle representation of a graph $G$ consists of a set of pairwise disjoint simply-connected closed regions and a one-to-one mapping of the vertices of $G$ to points such that two vertices are adjacent in $G$ if and only if the line segment conn
Externí odkaz:
http://arxiv.org/abs/2206.15414
In an upward-planar L-drawing of a directed acyclic graph (DAG) each edge $e$ is represented as a polyline composed of a vertical segment with its lowest endpoint at the tail of $e$ and of a horizontal segment ending at the head of $e$. Distinct edge
Externí odkaz:
http://arxiv.org/abs/2205.05627
Autor:
Chaplick, Steven, Di Giacomo, Emilio, Frati, Fabrizio, Ganian, Robert, Raftopoulou, Chrysanthi N., Simonov, Kirill
We obtain new parameterized algorithms for the classical problem of determining whether a directed acyclic graph admits an upward planar drawing. Our results include a new fixed-parameter algorithm parameterized by the number of sources, an XP-algori
Externí odkaz:
http://arxiv.org/abs/2203.05364
A rectangular dual of a plane graph $G$ is a contact representations of $G$ by interior-disjoint axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the union of all rectangles is a rectangle. A rectangular dual gives rise
Externí odkaz:
http://arxiv.org/abs/2112.03040