Structural parameters of Schnyder woods
Christian Ortlieb, Jens M. Schmidt · Discrete Mathematics · 2024
We study two fundamental parameters of Schnyder woods by exploiting structurally related methods. First, we prove a new lower bound on the total number of leaves in the three trees of a Schnyder wood. Second, it is well-known that Schnyder woods can be used to find three compatible ordered path partitions. We prove new lower bounds on the number of singletons , i.e. paths that consists of exactly one vertex, in such compatible ordered path partitions. All bounds that we present are tight.