Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. On the Page Number of Upward Planar Directed Acyclic Graphs
 
conference paper

On the Page Number of Upward Planar Directed Acyclic Graphs

Frati, Fabrizio  
•
Fulek, Radoslav  
•
Ruiz-Vargas, Andres J.  
2011
Proc. 19th International Symposium on Graph Drawing
19th International Symposium on Graph Drawing

In this paper we study the page number of upward planar directed acyclic graphs. We prove that: (I) the page number of any n-vertex upward planar triangulation G whose every maximal 4-connected component has page number k is at most min {O(k log n), O(2(k))1; (2) every upward planar triangulation G with o(n/log n) diameter has o(n) page number; and (3) every upward planar triangulation has a vertex ordering with o(n) page number if and only if every upward planar triangulation whose maximum degree is O(root n) does.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-642-25878-7_37
Web of Science ID

WOS:000307210800036

Author(s)
Frati, Fabrizio  
Fulek, Radoslav  
Ruiz-Vargas, Andres J.  
Date Issued

2011

Publisher

Springer-Verlag Berlin

Publisher place

Berlin

Published in
Proc. 19th International Symposium on Graph Drawing
ISBN of the book

978-3-642-25877-0

Total of pages

12

Series title/Series vol.

Lecture Notes in Computer Science; 7034

Start page

391

End page

402

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DCG  
Event nameEvent place
19th International Symposium on Graph Drawing

Eindhoven, Netherlands

Available on Infoscience
December 19, 2011
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/75813
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés