skip to main content
Ngôn ngữ:
Giới hạn tìm kiếm: Giới hạn tìm kiếm: Dạng tài nguyên Hiển thị kết quả với: Hiển thị kết quả với: Chỉ mục

Streamed Graph Drawing and the File Maintenance Problem

Goodrich, Michael T. ; Pszona, Paweł

Arxiv ID: 1308.6711

Toàn văn sẵn có

Trích dẫn Trích dẫn bởi
  • Nhan đề:
    Streamed Graph Drawing and the File Maintenance Problem
  • Tác giả: Goodrich, Michael T. ; Pszona, Paweł
  • Chủ đề: Computer Science - Data Structures And Algorithms ; F.2.2
  • Mô tả: In streamed graph drawing, a planar graph, G, is given incrementally as a data stream and a straight-line drawing of G must be updated after each new edge is released. To preserve the mental map, changes to the drawing should be minimized after each update, and Binucci et al.show that exponential area is necessary and sufficient for a number of streamed graph drawings for trees if edges are not allowed to move at all. We show that a number of streamed graph drawings can, in fact, be done with polynomial area, including planar streamed graph drawings of trees, tree-maps, and outerplanar graphs, if we allow for a small number of coordinate movements after each update. Our algorithms involve an interesting connection to a classic algorithmic problem - the file maintenance problem - and we also give new algorithms for this problem in a framework where bulk memory moves are allowed. Comment: 16 pages, 9 figures; to appear at the 21st International Symposium on Graph Drawing (GD 2013)
  • Số nhận dạng: Arxiv ID: 1308.6711

Đang tìm Cơ sở dữ liệu bên ngoài...