Scholarlink

We investigate a new structural property of Schnyder woods: every minimal Schnyder wood of a 3-connected planar graph of order n has a tree of depth at least \( \log _2(n)/(3 \log _2(3)) \) . This bound is tight. Our result directly implies that such a graph has an induced path of length at least \( \log _2(n)/(3 \log _2(3)) \) , improving the previous best lower bound on the length of such a path.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Minimal Schnyder Woods and Long Induced Paths in 3-Connected Planar Graphs

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Christian Ortlieb

摘要

We investigate a new structural property of Schnyder woods: every minimal Schnyder wood of a 3-connected planar graph of order n has a tree of depth at least \( \log _2(n)/(3 \log _2(3)) \) . This bound is tight. Our result directly implies that such a graph has an induced path of length at least \( \log _2(n)/(3 \log _2(3)) \) , improving the previous best lower bound on the length of such a path.