- A Planar Linear Arboricity Conjecture,
with Marek Cygan and Borut Luzar.
Proc. 7th International Conference on Algorithms and Complexity
(CIAC 2010), LNCS 6078, 2010, pp. 204-216.
arXiv:0912.5528, 2009.
[PDF] [Electronic version]
Abstract:
The linear arboricity la(G) of a graph G is the minimum number of linear
forests that partition the edges of G. In 1984, Akiyama et al. stated the
Linear Arboricity Conjecture (LAC), that the linear arboricity of any simple
graph of maximum degree Δ is either ⌈Δ/2⌉
or ⌈(Δ+1)/2⌉. J. L. Wu. and Y. W. Wu. proved that LAC
holds for all planar graphs.
LAC implies that for Δ odd, la(G)=⌈Δ/2⌉. We conjecture that for planar graphs this
equality is true also for any even Δ ≥ 6. (There are examples of
graphs with maximum degree 2 and 4 where la(G)>⌈Δ/2⌉.) In this paper we show
that it is true for any even Δ ≥ 10, leaving open only the cases
Δ=6, 8.
We present also an O(n log n)-time algorithm for partitioning a planar graph
into max{la(G),5} linear forests, which is optimal when Δ ≥ 9.
- An improved bound on the largest induced forests for triangle-free planar
graphs, with Borut Luzar and Riste Skrekovski
Discrete Mathematics & Theoretical Computer Science Vol. 12, No. 1, 87-100, 2010.
[PDF]
[BibTeX entry]
[Electronic version]
Abstract:
In 1979 Alberson and Berman raised a conjecture that every
n-vertex planar graph has an induced forest of size at least n/2.
Clearly, restricting the girth (the length of the shortest cycle)
of the graph should result in bigger
induced forests. In 1987 Akiyama and Watanabe conjectured that every
bipartite planar graph has an induced forest of size ≥5/8n.
The tight example is the cube Q3 and it seems that this bound can
hold even for all planar graph of girth at least 4.
Motivated by this, Salavatipour showed that every planar graph of girth at
least 4 contains an induced forest of size at least 17/32n + O(1).
We improve the bound of Salavatipour to 71/128n + O(1).
We also pose some questions regarding planar graphs of higher girth.
- Total colouring of plane graphs with maximum degree nine, with Jean-Sebastien Sereni and Riste
Skrekovski,
SIAM J. Discrete Math., Vol. 22, No. 4, 2008, 1462--1479.
[BibTeX entry]
[PDF]
[Electronic version]
Abstract:
The central problem of the total-colourings is the Total-Colouring
Conjecture, which asserts that every graph of maximum degree Δ
admits a (Δ + 2)-total-colouring. Similarly to edge-colourings --- with
Vizing's edge-colouring conjecture --- this bound can be decreased by
1 for plane graphs of higher maximum degree. More precisely, it is
known that if Δ ≥ 10 then every plane graph of maximum degree
Δ
is (Δ + 1)-totally-colourable. On the other hand, such a statement
does not hold if Δ ≤ 3. We prove that every plane graph of maximum
degree 9 can be 10-totally-coloured.
- New Linear-Time Algortihms for Edge-Coloring Planar Graphs,
with Richard Cole
Algorithmica, Vol. 50, No. 3, 2008, 351--368 .
[BibTeX entry]
[PS]
[PDF]
[Electronic version]
Abstract:
We show efficient algorithms for edge-coloring planar graphs.
Our main result is a linear-time algorithm for coloring planar graphs with
maximum degree Δ with max{Δ, 9} colors. Thus the coloring
is
optimal for graphs with maximum degree Δ ≥ 9. Moreover for
Δ=4,5,6 we give linear-time algorithms that use Δ+2 colors.
These results improve over the algorithms of Chrobak and
Yung [J. Alg., 1989] and of Chrobak and Nishizeki [J. Alg., 1990]
which color planar graphs using max{Δ, 19} colors in linear time
or using max{Δ, 9} colors in O(n log n) time.
- A Generalization of Kotzig's Theorem and its Application,
with Richard Cole, Riste Skrekovski,
SIAM J. Discrete Math., Vol. 21, No. 1, 2007, 93--106.
[BibTeX entry]
[PS]
[PDF]
[Electronic version]
Abstract:
An edge of a graph is light when the sum of the degrees of its
endvertices is at most 13.
The well-known Kotzig Theorem states that every 3-connected planar graph
contains a light edge. Later, Borodin extended this result
to the class of planar graphs of minimum degree at least 3.
We deal with generalizations of these results for planar graphs of minimum
degree 2.
Borodin, Kostochka and Woodall [JCTB, 1997] showed that each such
graph contains
a light edge or a member of two infinite sets of configurations, called
2-alternating cycles and 3-alternators. This implies that planar graphs with
maximum degree Δ ≥ 12 are Δ-edge-choosable.
We prove a similar result with 2-alternating cycles and 3-alternators
replaced
by five fixed bounded-sized configurations called crowns. This gives another
proof of Δ-edge-choosability of planar graphs with Δ ≥ 12.
However, we show efficient choosability, i.e. we describe a
linear-time algorithm for max{Δ, 12}-edge-list-coloring planar
graphs. This extends the result of Chrobak and Yung [J. Alg., 1989].
- Oracles for Bounded Length Shortest Paths in Planar Graphs, with Maciej
Kurowski
ACM Transactions on Algorithms, Vol. 2, No. 3, 2006, 335-363.
[BibTeX entry]
[PS]
[PDF]
[Electronic version]
Abstract:
We present a new approach for answering short path queries in
planar graphs.
For any fixed constant k and a given unweighted planar graph G=(V,E) one
can build
in O(|V|) time a data structure,
which allows to check in O(1) time whether two given vertices
are at distance at most k in G and if so a shortest path between them is
returned. Graph G may be undirected as well as directed.
Our data structure works in fully dynamic environment. It can be updated in
O(1) time after removing an edge or a vertex while updating
after an edge insertion takes polylogarithmic amortized time.
Our results can be easily generalized to other wide classes of graphs -- for
instance we can take any minor-closed family of graphs.
- Fast 3-Coloring Triangle-Free Planar Graphs,
Full version: Algorithmica (in press, published on-line)
[PDF]
[Electronic version]
Conference version: Proc. 12th Annual European Symposium on Algorithms
(ESA 2004),
LNCS
3221, 2004, 436-447.
[BibTeX entry]
[Electronic version]
Abstract:
Although deciding whether the vertices of a planar graph can be colored with
three colors is NP-hard, the widely known Grötzsch's theorem states that
every triangle-free planar graph is 3-colorable.
We show the first o(n^2) algorithm for 3-coloring vertices of
triangle-free planar graphs. The time complexity of the algorithm is
O(n log n).
Note: In 2009, Dvorak, Kawarabayashi and Thomas
showed a linear-time algorithm (see here).
- More on Light Graphs in 3-Connected Plane Graphs Without
Triangular or Quadrangular Faces,
Technical Report no. 275,
Institute of Informatics, Warsaw University, 2004.
[BibTeX entry]
[PS]
[PDF]
Abstract:
Intuitively, a graph H is light in a class Q of graphs when H
is a subgraph of some member of Q
and for every G ∈ Q if G contains H as a subgraph,
there is also an occurence H' of H in G such that the degrees of
vertices of H' in G are bounded by some constant. Characterizing light
graphs
in various subclasses of plane graphs attracted many researchers in recent
years.
We focus on the class P(3,5) of 3-connected plane graphs with
faces of length at least 5.
The class was previously studied by S. Jendrol' and P. J.
Owens who
showed that every k-cycle, k > 5 and k ≠ 14, is not light in
P(3,5). They
also proved that every block of any light graph in P(3,5) has at
most
18 vertices.
In this paper we show that every block of a light graph in P(3,5) is a
bridge, a cycle C5 or a cycle C14.
Very recently, T. Madaras showed that K1,3 is light in P(3,5).
This is an immediate
corollary from more
general result stating that in every planar graph with faces of length
≥5 and vertices
of degree ≥3 there exists a vertex of degree at most 3 with neighbors
a,b,c
such that deg(a)=deg(b)=3 and deg(c) ≤ 4. We give a new, much
shorter proof
of the latter result.
- Short Cycles in Planar Graphs,
Proc. 29th Workshop Graph-Theoretic Concepts in Comp. Sci. (WG
2003),
LNCS
2880, 2003, 284-296.
[BibTeX entry]
[PS]
[PDF]
[Electronic version]
Abstract:
We present new algorithms for finding short cycles (of length at most 6) in
planar graphs. Although there is an O(n)-time algorithm for finding
any
fixed subgraph H in a given n-vertex planar graph (Eppstein, JGAA, 1999), the
multiplication constant
hidden in "O" notation (which depends on the size of H) is so high,
that it rather cannot be used in practice even when |V(H)| = 4.
Our approach gives faster "practical algorithms", still of linear time
complexity, which are additionally
much easier to implement.
As a side-effect of our approach we show that the maximum number of
k-cycles
in n-vertex planar graph is Θ(n⌊k/2⌋).
- Short Path Queries in Planar Graphs in Constant Time,
with M.Kurowski,
Proc. 35th Symp. Theory of
Computing (STOC 2003),
2003, 143-148.
[BibTeX entry]
[PS]
[PDF]
[Electronic version]
Note: This is a preliminary, conference version of the paper "Oracles
for Bounded Length Shortest Paths in Planar Graphs", TALG 2006.
Abstract:
We present a new algorithm for answering short path queries in
planar graphs.
For any fixed constant k and a given unweighted planar graph G=(V,E) one
can build in O(|V|) time a data structure,
which allows to check in O(1) time whether two given vertices
are distant by at most k in G and if so a shortest path between them is
returned.
- A New 3-Color Criterion For Planar Graphs, with K. Diks and M.
Kurowski,
Proc. 28th Workshop Graph-Theoretic Concepts in Comp. Sci. (WG 2002),
LNCS 2573, 2002, 138-149.
[BibTeX entry]
[PS]
[PDF]
[Electronic version]
Abstract:
We present a new general 3-color criterion for planar graphs.
This criterion easily implies several known sufficent 3-colorability
conditions, as well as some new consequences, namely:
- A near-traingulation (plane graph with at most one non-triangular face)
is 3-colorable iff every vertex not incident with the non-triangular face
has even degree.
- A sufficient and necessary 3-colorability condition for triangulations
with holes (plane graphs such that each vertex is incident with at most one
non-triangular face). Such a graph is 3-colorable iff
- every vertex not incident with the non-triangular face has even degree.
- for each non-triangular face f, when we paint the edges incident with
f in black and white so that the color changes only
in odd-degree vertices, then the numbers of black and white edges are
congruent modulo 3.