4 hasil
Menampilkan 1–4 · 0,05 detik · RSS
Journal of Graph Algorithms and Applications
Scopus
ISSN 1526-1719 · Brown University · 4 artikel di indeks
-
Artikel Jurnal
On Shortest Path, BFS- and DFS-Tree Graphs
Flip graphs encode the structure of feasible transformations between combinatorial objects, making them a fundamental tool in reconfiguration problems. Tree graphs, which are flip graphs whose nodes represent the spanning trees of a graph, have received significant attention due to their…
-
Artikel Jurnal
Visualizing Treewidth
A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth. Our approach draws the tree decomposition or path decomposition as a…
-
Artikel Jurnal
A New Simple Algorithm for Computing Maximum Weight Induced Forests in Circle Graphs
This paper describes a new, simple algorithm for computing a maximum weight induced forest in a circle graph. The algorithm requires $O(n^3 m)$ time and $O(n^3)$ space. In the unweighted case, an algorithm operating in $O(n^2 mk)$ time and $O(nk^2)$ space is described, where $k$ is the cardinality…
-
Artikel Jurnal
Improving the Crossing Lemma by Characterizing Dense 2-Planar and 3-Planar Graphs
The classical Crossing Lemma by Ajtai et al.~and Leighton from 1982 gave an important lower bound of $c \frac{m^3}{n^2}$ for the number of crossings in any drawing of a given graph of $n$ vertices and $m$ edges. The original value was $c= 1/100$, which then has gradually been improved. Here, the…