Results 41 to 50 of about 2,549 (154)
On first-order transductions of classes of graphs [PDF]
Logical Methods in Computer ScienceWe study various aspects of the first-order transduction quasi-order on graph classes, which provides a way of measuring the relative complexity of graph classes based on whether one can encode the other using a formula of first-order (FO) logic.
Samuel Braunfeld +3 more
doaj +1 more source
Discrete Mathematics & Theoretical Computer ScienceNot 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 the
Patrizio Angelini +10 more
doaj +1 more source
Pathwidth, trees, and random embeddings [PDF]
Combinatorica, 2013 We prove that, for every $k=1,2,...,$ every shortest-path metric on a graph of pathwidth $k$ embeds into a distribution over random trees with distortion at most $c$ for some $c=c(k)$. A well-known conjecture of Gupta, Newman, Rabinovich, and Sinclair states that for every minor-closed family of graphs $F$, there is a constant $c(F)$ such that the ...
Lee, James R., Sidiropoulos, Anastasios
openaire +3 more sources
The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
, 2014 We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex ...
Hatanaka, Tatsuhiko +2 more
core +1 more source
Digraph Complexity Measures and Applications in Formal Language Theory [PDF]
, 2011 We investigate structural complexity measures on digraphs, in particular the cycle rank. This concept is intimately related to a classical topic in formal language theory, namely the star height of regular languages.
Hermann Gruber +1 more
core +4 more sources
Width, Depth, and Space: Tradeoffs between Branching and Dynamic Programming
Algorithms, 2018 Treedepth is a well-established width measure which has recently seen a resurgence of interest. Since graphs of bounded treedepth are more restricted than graphs of bounded tree- or pathwidth, we are interested in the algorithmic utility of this ...
Li-Hsuan Chen +3 more
doaj +1 more source
SIAM Journal on Discrete MathematicsThe {\em circumference} of a graph $G$ with at least one cycle is the length of a longest cycle in $G$. A classic result of Birmelé (2003) states that the treewidth of $G$ is at most its circumference minus $1$. In case $G$ is $2$-connected, this upper bound also holds for the pathwidth of $G$; in fact, even the treedepth of $G$ is upper bounded by its
Marcin Briański +2 more
openaire +2 more sources
An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains
, 2012 It is known that the First-Fit algorithm for partitioning a poset P into chains uses relatively few chains when P does not have two incomparable chains each of size k. In particular, if P has width w then Bosek, Krawczyk, and Szczypka (SIAM J.
Bosek B. +8 more
core +1 more source
Packing independent cliques into planar graphs
Theory and Applications of GraphsThe indeque number of a graph is largest set of vertices that induce an independent set of cliques. We study the extremal value of this parameter for the class and subclasses of planar graphs, most notably for forests and graphs of pathwidth at most $2$.
Csaba Biró +2 more
doaj +1 more source