Youngho Yoo

dblp:197/1416 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
2since 2021 · last 2025
0000-0003-3394-422XORCID · corroborated

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

Theory of computation · 2 · 2 since 2021
YearPublicationVenuePosition
2025 Disjoint Paths Problem with Group-Expressable Constraints
Chun-Hung Liu, Youngho Yoo
STOC2
2025 Chasing Tripods to Obtain a Rooted Subdivision
abstract
Abstract. A tripod with feet [Formula: see text] is obtained by six internally disjoint paths, three of them starting at a single vertex [Formula: see text] and ending at [Formula: see text], and another three of them starting at another vertex [Formula: see text] and ending at [Formula: see text]. Tripods play an important role in the proof of the two paths theorem, as well as some other structure theorems concerning rooted minors. The complete characterization of a tripod is well-known; if we cannot get such a tripod, then assuming some mild connectivity, a given graph must be embedded in a plane with [Formula: see text] in the outer face boundary. In this paper, by using the tripod result as a base, we give a structure theorem that, given four vertices [Formula: see text] in a graph [Formula: see text], guarantees a subgraph of [Formula: see text] that is homeomorphic to a subgraph of [Formula: see text] and contains at least three of [Formula: see text] as branches. This result is also motivated by the following problem: Every minimum counterexample to Hajós’ conjecture for [Formula: see text] is internally 5-connected.
Koyo Hayashi, Ken-ichi Kawarabayashi, Youngho Yoo
SIAM J. Discret. Math.3