Christian Ortlieb

dblp:319/0066 · DBLP profile ↗
← Back
4ranked-venue papers
4as first author
4since 2021 · last 2025
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 3 first-author · 3 since 2021Applied, interdisciplinary, general and emerging computing · 1 · 1 first-author · 1 since 2021
YearPublicationVenuePosition
2025 Minimal Schnyder Woods and Long Induced Paths in 3-Connected Planar Graphs
Christian Ortlieb
SOFSEM (2)1
2025 Toward Grünbaum's conjecture bounding vertices of degree 4
abstract
• We consider spanning trees and their co-trees in 3-connected planar graphs. • We give a spanning tree such that the tree and its co-tree have maximum degree 4. • Additionally, we provide an upper bound on the number of vertices of degree 4. • This is the best known result toward a solution of a conjecture of Gr̎unbaum of 1970. Given a spanning tree T of a planar graph G , the co-tree of T is the spanning tree of the dual graph G * with edge set ( E ( G ) − E ( T ) ) * . Grünbaum conjectured in 1970 that every planar 3-connected graph G contains a spanning tree T such that both T and its co-tree have maximum degree at most 3. While Grünbaum’s conjecture remains open, Schmidt and the author recently improved the upper bound on the maximum degree from 5 (Biedl 2014) to 4. In this paper, we modify this approach taking a further step towards Grünbaum’s conjecture. We again obtain a spanning tree T such that both T and its co-tree have maximum degree at most 4 and, additionally, an upper bound on the number of vertices of degree 4 of T and its co-tree.
Christian Ortlieb
Theor. Comput. Sci.1
2024 Schnyder Woods and Long Induced Paths in 3-Connected Planar Graphs
Christian Ortlieb
LATIN (2)1
2024 Toward Grünbaum's Conjecture for 4-Connected Graphs
Christian Ortlieb
MFCS1