Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2020-002 (April 13, 2020)

Path-monotonic Upward Drawings of Plane Graphs
by Seok-Hee Hong, Hiroshi Nagamochi

pdf File


In this paper, we introduce a new problem of finding an upward drawing of a given plane graph G with a set P of paths so that each path in the set is drawn as a poly-line that is monoton in the y-coordinate. We present a sufficient condition for an instance (G,P) to admit such an upward drawing. Our results imply that every 1-plane graph admits an upward drawing.