Stephen G Kobourov

Interests

Research

Design and analysis of algorithms, geometric algorithms, algorithm engineering, graph theory, information visualization, human computer interaction, graph drawing, and network visualization

Teaching

Algorithms, Theory of Computing, Graph Theory, Information Visualization, Computational Geometry, Data Structures

Courses

Scholarly Contributions

Chapters

• Kobourov, S. G. (2016). Canonical Orders and Schnyder Realizers. In Encyclopedia of Algorithms(pp 277--283).
• Kobourov, S. G. (2015). Canonical Orders and Schnyder Realizers. In Encyclopedia of Algorithms(pp 1-8). Springer. doi:10.1007/978-3-642-27848-8_650-1
• Bl"asius, T., Kobourov, S. G., & Rutter, I. (2014). Simultaneous Embedding of Planar Graphs. In Handbook of Graph Drawing and Visualization(pp 349-381). CRC Press.
• Kobourov, S. G. (2014). Force-Directed Drawing Algorithms. In Handbook of Graph Drawing and Visualization(pp 383-408). CRC Press.

Journals/Publications

• Chen, H., Kobourov, S. G., Maciejewski, R., Lu, Y., Huroyan, V., & Soni, U. (2021). Same Stats, Different Graphs: Exploring the Space of Graphs in Terms of Graph Properties. IEEE transactions on visualization and computer graphics, 27(3), 2056-2072. doi:https://doi.org/10.1109/TVCG.2019.2946558
  More info

  This journal is ranked A in CORE
• De, L. F., Di, G. E., Hong, S., Kobourov, S., Lenhart, W., Liotta, G., Meijer, H., Tappini, A., & Wismath, S. (2021). Packing Trees into 1-planar Graphs. Journal of Graph Algorithms and Applications, 25(1), 605-624. doi:https://doi.org/10.7155/jgaa.00574
• Evans, W., Felsner, S., Kleist, L., & Kobourov, S. G. (2021). On Area-Universal Quadrangulations. Journal of Graph Algorithms and Applications, 25(1), 171-193. doi:DOI: 10.7155/jgaa.00555
• Hossain, I., Huroyan, V., Kobourov, S. G., & Navarrete, R. (2021). Multi-Perspective, Simultaneous Embedding. IEEE Transactions on Visualization and Computer Graphics, 27(2), 1569-1579. doi:https://doi.org/10.1109/TVCG.2020.3030373
  More info

  This journal is ranked A in CORE.
• Jacobsen, B., Wallinger, M., Kobourov, S. G., & Noellenburg, M. (2021). MetroSets: Visualizing Sets as Metro Maps. IEEE Transactions on Visualization and Computer Graphics, 27(2), 1257-1267. doi:https://doi.org/10.1109/TVCG.2020.3030475
  More info

  This journal is ranked A in CORE.
• Sahneh, F., Balk, M. A., Kisley, M., Chan, C. K., Fox, M., Nord, B., Lyons, E., Swetnam, T., Huppenkothen, D., Sutherland, W., Walls, R. L., Quinn, D. P., Tarin, T., LeBauer, D., Ribes, D., Birnie, D. P., Lushbough, C., Carr, E., Nearing, G., , Fischer, J., et al. (2021). Ten simple rules to cultivate transdisciplinary collaboration in data science. PLoS computational biology, 17(5), e1008879.
• Wallinger, M., Jacobsen, B., Kobourov, S. G., & Noellenburg, M. (2021). On the Readability of Abstract Set Visualizations. IEEE Transactions on Visualization and Computer Graphics, 27(6), 2821-2832. doi:https://doi.org/10.1109/TVCG.2021.3074615
  More info

  This journal is ranked A in CORE.
• Ahmed, A. R., Bodwin, G., Sahneh, F. D., Hamm, K., Jebelli, M., Kobourov, S. G., & Spence, R. (2020). Graph spanners: A tutorial review. Computer Science Review, 37. doi:https://doi.org/10.1016/j.cosrev.2020.100253
• Angelini, P., Eades, P., Hong, S., Klein, K., Kobourov, S. G., Liotta, G., Navarra, A., & Tappini, A. (2020). Graph Planarity by Replacing Cliques with Paths. Journal of Algorithms, 13(8). doi:https://doi.org/10.3390/a13080194
• Ahmed, A. R., Rahman, M. S., & Kobourov, S. (2019). Online facility assignment. Theoretical Computer Science.
  More info

  This journal is ranked A in CORE
• Ahmed, R., Angelini, P., Sahneh, F. D., Efrat, A., Glickenstein, D., Gronemann, M., Heinsohn, N., Kobourov, S. G., Spence, R., Watkins, J., & others, . (2019). Multi-level Steiner trees. Journal of Experimental Algorithmics (JEA), 24(1), 1--22.
  More info

  This journal is ranked A in CORE
• Kobourov, S. G., Kindermann, P., Loeffler, M., Noellenburg, M., Vogtenhuber, B., & Schulz, A. (2019). Lombardi drawings of knots and links. Journal of Computational Geometry, 10(1), 444-476. doi:https://doi.org/10.20382/jocg.v10i1a15
• Luca, F. D., Giacomo, E. D., Didimo, W., Kobourov, S. G., & Liotta, G. (2019). An Experimental Study on the Ply Number of Straight-line Drawings. J. Graph Algorithms Appl., 23(1), 71--91.
• Luca, F. D., Hossain, M. I., Kobourov, S. G., Lubiw, A., & Mondal, D. (2019). Recognition and drawing of stick graphs. Theor. Comput. Sci., 796, 22--33.
  More info

  This journal is ranked A in CORE
• Okoe, M., Jianu, R., & Kobourov, S. G. (2019). Node-Link or Adjacency Matrices: Old Question, New Insights. IEEE Trans. Vis. Comput. Graph., 25(10), 2940--2952.
  More info

  This journal is ranked A in CORE
• Chimani, M., Felsner, S., Kobourov, S. G., Ueckerdt, T., Valtr, P., & Wolff, A. (2018). On the Maximum Crossing Number. J. Graph Algorithms Appl., 22(1), 67--87.
• Das, A., Fleszar, K., Kobourov, S. G., Spoerhase, J., Veeramoni, S., & Wolff, A. (2016). Approximating the Generalized Minimum Manhattan Network Problem. Algorithmica. doi:10.1007/s00453-017-0298-0
  More info

  This journal is ranked A* in CORE.
• Das, A., Fleszar, K., Kobourov, S. G., Spoerhase, J., Veeramoni, S., & Wolff, A. (2018). Approximating the Generalized Minimum Manhattan Network Problem. Algorithmica, 80(4), 1170--1190.
  More info

  This journal is ranked A* in CORE
• Duncan, C. A., Eppstein, D., Goodrich, M. T., Kobourov, S. G., L"{o}ffler, M., & N"{o}llenburg, M. (2018). Planar and poly-arc Lombardi drawings. JoCG, 9(1), 328--355.
• Eppstein, D., Kindermann, P., Kobourov, S. G., Liotta, G., Lubiw, A., Maignan, A., Mondal, D., Vosoughpour, H., Whitesides, S., & Wismath, S. K. (2018). On the Planar Split Thickness of Graphs. Algorithmica, 80(3), 977--994.
  More info

  This journal is ranked A* in CORE
• Evans, W. S., Felsner, S., Kaufmann, M., Kobourov, S. G., Mondal, D., Nishat, R. I., & Verbeek, K. (2018). Table cartogram. Comput. Geom., 68, 174--185.
• Nusrat, S., Alam, M. J., & Kobourov, S. G. (2018). Evaluating Cartogram Effectiveness. IEEE Trans. Vis. Comput. Graph., 24(2), 1077--1090.
  More info

  This journal is ranked A in CORE
• Nusrat, S., Alam, M. J., Scheidegger, C., & Kobourov, S. G. (2018). Cartogram Visualization for Bivariate Geo-Statistical Data. IEEE Trans. Vis. Comput. Graph., 24(10), 2675--2688.
  More info

  This journal is ranked A in CORE
• Okoe, M., Jianu, R., & Kobourov, S. G. (2018). Node-link or Adjacency Matrices: Old Question, New Insights. IEEE transactions on visualization and computer graphics. doi:10.1109/TVCG.2018.2865940
  More info

  This journal is ranked A in CORE
• Rains, S. A., Hingle, M. D., Surdeanu, M., Bell, D., & Kobourov, S. (2019). A Test of The Risk Perception Attitude Framework as a Message Tailoring Strategy to Promote Diabetes Screening. Health communication, 34(6), 672-679. doi:https://doi.org/10.1080/10410236.2018.1431024
• Simonetto, P., Archambault, D., & Kobourov, S. G. (2018). Event-Based Dynamic Graph Visualisation. IEEE transactions on visualization and computer graphics. doi:10.1109/TVCG.2018.2886901
  More info

  This journal is ranked A in CORE
• Soni, U., Lu, Y., Hansen, B., Purchase, H. C., Kobourov, S. G., & Maciejewski, R. (2018). The Perception of Graph Properties in Graph Layouts. Comput. Graph. Forum, 37(3), 169--181.
• Zhou, J., Bell, D., Nusrat, S., Hingle, M., Surdeanu, M., & Kobourov, S. (2018). Calorie Estimation From Pictures of Food: Crowdsourcing Study.. Journal of Medical Internet Research, 7(2), 17–37.
• Alam, M. J., Chaplick, S., Fijavz, G., Kaufmann, M., Kobourov, S. G., Pupyrev, S., & Toeniskoetter, J. (2017). Threshold-coloring and unit-cube contact representation of planar graphs. Discrete Applied Mathematics, 216, 2--14.
• Alam, M. J., Kobourov, S. G., & Mondal, D. (2016). Orthogonal Layout with Optimal Face Complexity. Computational Geometry: Theory and Applications, 63, 40-52. doi:https://doi.org/10.1016/j.comgeo.2017.02.005
• Alam, M. J., Kobourov, S. G., & Mondal, D. (2017). Orthogonal layout with optimal face complexity. Comput. Geom., 63, 40--52.
• Angelini, P., Bekos, M. A., Luca, F. D., Didimo, W., Kaufmann, M., Kobourov, S. G., Montecchiani, F., Raftopoulou, C. N., Roselli, V., & Symvonis, A. (2017). Vertex-Coloring with Defects. J. Graph Algorithms Appl., 21(3), 313--340.
• Bekos, M. A., Dijk, T. C., Fink, M., Kindermann, P., Kobourov, S. G., Pupyrev, S., Spoerhase, J., & Wolff, A. (2017). Improved Approximation Algorithms for Box Contact Representations. Algorithmica, 77(3), 902--920.
  More info

  This journal is ranked A* in CORE.
• Bekos, M., Kobourov, S. G., Kaufmann, M., & Veeramoni, S. (2016). The Maximum k-Differential Coloring Problem. Journal of Discrete Algorithms, 45, 35-53. doi:https://doi.org/10.1016/j.jda.2017.08.001
• Kobourov, S. G., Liotta, G., & Montecchiani, F. (2017). An annotated bibliography on 1-planarity. Computer Science Review, 25, 49--67.
• Kruiger, J. F., Rauber, P. E., Martins, R. M., Kerren, A., Kobourov, S. G., & Telea, A. (2017). Graph Layouts by t-SNE. Comput. Graph. Forum, 36(3), 283--294.
• Welch, E., & Kobourov, S. G. (2017). Measuring Symmetry in Drawings of Graphs. Computer Graphics Forum, 36(3), 341--351.
• Alam, M. J., Chaplick, S., Fijavz, G., Kaufmann, M., Kobourov, S. G., Pupyrev, S., & Toeniskoetter, J. (2016). Threshold-coloring and unit-cube contact representation of planar graphs. DISCRETE APPLIED MATHEMATICS, 216, 2-14.
• Bekos, M. A., Dijk, T. C., Fink, M., Kindermann, P., Kobourov, S., Pupyrev, S., Spoerhase, J., & Wolff, A. (2016). Improved Approximation Algorithms for Box Contact Representations. Algorithmica, 77(3), 902--920.
  More info

  This journal is ranked A* in CORE.
• Emmons, S., Kobourov, S., Gallant, M., & Borner, K. (2016). Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale. PLOS ONE, 11(7).
• Nusrat, S., & Kobourov, S. (2016). The State of the Art in Cartograms. COMPUTER GRAPHICS FORUM, 35(3), 619-642.
• Nusrat, S., Alam, M. J., & Kobourov, S. G. (2016). Evaluating Cartogram Effectiveness. IEEE Transacations on Visualization and Computer Graphics.
  More info

  This journal is ranked A* in CORE.
• Saket, B., Scheidegger, C., & Kobourov, S. (2016). Comparing Node-Link and Node-Link-Group Visualizations From An Enjoyment Perspective. COMPUTER GRAPHICS FORUM, 35(3), 41-50.
• Alam, M. J., Kaufmann, M., Kobourov, S. G., & Mchedlidze, T. (2015). Fitting Planar Graphs on Planar Maps. J. Graph Algorithms Appl., 19, 413--440.
• Alam, M. J., Kobourov, S. G., & Veeramoni, S. (2015). Quantitative Measures for Cartogram Generation Techniques. Comput. Graph. Forum, 34, 351--360.
• Angelini, P., Didimo, W., Kobourov, S. G., Mchedlidze, T., Roselli, V., Symvonis, A., & Wismath, S. K. (2015). Monotone Drawings of Graphs with Fixed Embedding. Algorithmica, 71, 233--257.
• Das, A., Gansner, E. R., Kaufmann, M., Kobourov, S. G., Spoerhase, J., & Wolff, A. (2015). Approximating Minimum Manhattan Networks in Higher Dimensions. Algorithmica, 71, 36--52.
• Efrat, A., Hu, Y., Kobourov, S. G., & Pupyrev, S. (2015). MapSets: Visualizing Embedded and Clustered Graphs. J. Graph Algorithms Appl., 19, 571--593.
• Saket, B., Scheidegger, C., Kobourov, S. G., & B{"{o}}rner, K. (2015). Map-based Visualizations Increase Recall Accuracy of Data. Comput. Graph. Forum, 34, 441--450.
• Abello, J., Archambault, D., Kennedy, J., Kobourov, S., Ma, K. L., Miksch, S., Muelder, C., & Telea, A. (2014). Temporal multivariate networks. Multivariate Network Visualization, 151--175.
• Alam, M. J., Kaufmann, M., Kobourov, S. G., & McHedlidze, T. (2014). Fitting planar graphs on planar maps. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8327 LNCS, 52-64.
  More info

  Abstract: Graph and cartographic visualization have the common objective to provide intuitive understanding of some underlying data. We consider a problem that combines aspects of both by studying the problem of fitting planar graphs on planar maps. After providing an NP-hardness result for the general decision problem, we identify sufficient conditions so that a fit is possible on a map with rectangular regions. We generalize our techniques to non-convex rectilinear polygons, where we also address the problem of efficient distribution of the vertices inside the map regions. © 2014 Springer International Publishing Switzerland.
• Bekos, M. A., Kaufmann, M., Kobourov, S. G., & Veeramoni, S. (2014). A note on maximum differential coloring of planar graphs. J. Discrete Algorithms, 29, 1--7.
• Bekos, M., Kaufmann, M., Kobourov, S., & Veeramoni, S. (2014). A note on maximum differential coloring of planar graphs. Journal of Discrete Algorithms, 29, 1--7.
• Saket, B., Simonetto, P., Kobourov, S. G., & B"orner, K. (2014). Node, Node-Link, and Node-Link-Group Diagrams: An Evaluation. IEEE Trans. Vis. Comput. Graph., 20(12), 2231--2240.
• Yifan, H. u., Kobourov, S. G., & Veeramoni, S. (2014). Embedding, clustering and coloring for dynamic maps. Journal of Graph Algorithms and Applications, 18(1), 77-109.
  More info

  Abstract: We describe a practical approach for visualizing multiple relationships defined on the same dataset using a geographic map metaphor, where clusters of nodes form countries and neighboring countries correspond to nearby clusters. Our aim is to provide a visualization that allows us to compare two or more such maps (showing an evolving dynamic process, or obtained using different relationships). In the case where we are considering multiple relationships, e.g., different similarity metrics, we also provide an interactive tool to visually explore the effect of combining two or more such relationships. Our method ensures good readability and mental map preservation, based on dynamic node placement with node stability, dynamic clustering with cluster stability, and dynamic coloring with color stability.
• Alam, M. J., & Kobourov, S. G. (2013). Proportional contact representations of 4-connected planar graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7704 LNCS, 211-223.
  More info

  Abstract: In a contact representation of a planar graph, vertices are represented by interior-disjoint polygons and two polygons share a non-empty common boundary when the corresponding vertices are adjacent. In the weighted version, a weight is assigned to each vertex and a contact representation is called proportional if each polygon realizes an area proportional to the vertex weight. In this paper we study proportional contact representations of 4-connected internally triangulated planar graphs. The best known lower and upper bounds on the polygonal complexity for such graphs are 4 and 8, respectively. We narrow the gap between them by proving the existence of a representation with complexity 6. We then disprove a 10-year old conjecture on the existence of a Hamiltonian canonical cycle in a 4-connected maximal planar graph, which also implies that a previously suggested method for constructing proportional contact representations of complexity 6 for these graphs will not work. Finally we prove that it is NP-hard to decide whether a 4-connected planar graph admits a proportional contact representation using only rectangles. © 2013 Springer-Verlag.
• Alam, M. J., Biedl, T., Felsner, S., Gerasch, A., Kaufmann, M., & Kobourov, S. G. (2013). Linear-time algorithms for hole-free rectilinear proportional contact graph representations. Algorithmica, 67(1), 3-22.
  More info

  Abstract: In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. In this paper we first study proportional contact representations that use rectilinear polygons without wasted areas (white space). In this setting, the best known algorithm for proportional contact representation of a maximal planar graph uses 12-sided rectilinear polygons and takes O(nlogn) time. We describe a new algorithm that guarantees 10-sided rectilinear polygons and runs in O(n) time. We also describe a linear-time algorithm for proportional contact representation of planar 3-trees with 8-sided rectilinear polygons and show that this is optimal, as there exist planar 3-trees that require 8-sided polygons. We then show that a maximal outer-planar graph admits a proportional contact representation using rectilinear polygons with 6 sides when the outer-boundary is a rectangle and with 4 sides otherwise. Finally we study maximal series-parallel graphs. Here we show that O(1)-sided rectilinear polygons are not possible unless we allow holes, but 6-sided polygons can be achieved with arbitrarily small holes. © 2013 Springer Science+Business Media New York.
• Alam, M. J., Biedl, T., Felsner, S., Kaufmann, M., Kobourov, S. G., & Ueckerdt, T. (2013). Computing Cartograms with Optimal Complexity. Discrete and Computational Geometry, 50(3), 784-810.
  More info

  Abstract: In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an area-universal rectangular layout in linear time. The exact cartogram can be computed from the area-universal layout with numerical iteration, or can be approximated with a hill-climbing heuristic. We also describe an alternative construction of cartograms for Hamiltonian maximal planar graphs, which allows us to directly compute the cartograms in linear time. Moreover, we prove that even for Hamiltonian graphs 8-sided rectilinear polygons are necessary, by constructing a non-trivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is one-legged, as in outer-planar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outer-planar graphs. Finally we address the problem of constructing small-complexity cartograms for 4-connected graphs (which are Hamiltonian). We first disprove a conjecture, posed by two set of authors, that any 4-connected maximal planar graph has a one-legged Hamiltonian cycle, thereby invalidating an attempt to achieve a polygonal complexity 6 in cartograms for this graph class. We also prove that it is NP-hard to decide whether a given 4-connected plane graph admits a cartogram with respect to a given weight function. © 2013 Springer Science+Business Media New York.
• Alam, M. J., Brandenburg, F. J., & Kobourov, S. G. (2013). Straight-line grid drawings of 3-connected 1-planar graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8242 LNCS, 83-94.
  More info

  Abstract: A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. In general, 1-planar graphs do not admit straight-line drawings. We show that every 3-connected 1-planar graph has a straight-line drawing on an integer grid of quadratic size, with the exception of a single edge on the outer face that has one bend. The drawing can be computed in linear time from any given 1-planar embedding of the graph. © 2013 Springer International Publishing Switzerland.
• Angelini, P., Didimo, W., Kobourov, S., Mchedlidze, T., Roselli, V., Symvonis, A., & Wismath, S. (2013). Monotone Drawings of Graphs with Fixed Embedding. Algorithmica, 1-25.
  More info

  Abstract: A drawing of a graph is a monotone drawing if for every pair of vertices u and v there is a path drawn from u to v that is monotone in some direction. In this paper we investigate planar monotone drawings in the fixed embedding setting, i.e., a planar embedding of the graph is given as part of the input that must be preserved by the drawing algorithm. In this setting we prove that every planar graph on n vertices admits a planar monotone drawing with at most two bends per edge and with at most 4 n-10 bends in total; such a drawing can be computed in linear time and requires polynomial area. We also show that two bends per edge are sometimes necessary on a linear number of edges of the graph. Furthermore, we investigate subclasses of planar graphs that can be realized as embedding-preserving monotone drawings with straight-line edges. In fact, we prove that biconnected embedded planar graphs and outerplane graphs always admit such drawings, and describe linear-time drawing algorithms for these two graph classes. © 2013 Springer Science+Business Media New York.
• Bekos, M. A., Kaufmann, M., Kobourov, S. G., & Symvonis, A. (2013). Smooth orthogonal layouts. Journal of Graph Algorithms and Applications, 17(5), 575-595.
  More info

  Abstract: We study the problem of creating smooth orthogonal layouts for planar graphs. While in traditional orthogonal layouts every edge is made of a sequence of axis-aligned line segments, in smooth orthogonal layouts every edge is made of axis-aligned segments and circular arcs with common tangents. Our goal is to create such layouts with low edge complexity, measured by the number of line and circular arc segments. We show that every 4-planar graph has a smooth orthogonal layout with edge complexity 3. If the input graph has a complexity-2 traditional orthogonal layout, we can transform it into a smooth complexity-2 layout. Using the Kandinsky model for removing the degree restriction, we show that any planar graph has a smooth complexity-2 layout.
• Bekos, M. A., Kaufmann, M., Kobourov, S. G., & Symvonis, A. (2013). Smooth orthogonal layouts. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7704 LNCS, 150-161.
  More info

  Abstract: We study the problem of creating smooth orthogonal layouts for planar graphs. While in traditional orthogonal layouts every edge is made of a sequence of axis-aligned line segments, in smooth orthogonal layouts every edge is made of axis-aligned segments and circular arcs with common tangents. Our goal is to create such layouts with low edge complexity, measured by the number of line and circular arc segments. We show that every biconnected 4-planar graph has a smooth orthogonal layout with edge complexity 3. If the input graph has a complexity-2 traditional orthogonal layout, we can transform it into a smooth complexity-2 layout. Using the Kandinsky model for removing the degree restriction, we show that any planar graph has a smooth complexity-2 layout. © 2013 Springer-Verlag.
• Bremner, D., Evans, W., Frati, F., Heyer, L., Kobourov, S. G., Lenhart, W. J., Liotta, G., Rappaport, D., & Whitesides, S. H. (2013). On representing graphs by touching cuboids. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7704 LNCS, 187-198.
  More info

  Abstract: We consider contact representations of graphs where vertices are represented by cuboids, i.e. interior-disjoint axis-aligned boxes in 3D space. Edges are represented by a proper contact between the cuboids representing their endvertices. Two cuboids make a proper contact if they intersect and their intersection is a non-zero area rectangle contained in the boundary of both. We study representations where all cuboids are unit cubes, where they are cubes of different sizes, and where they are axis-aligned 3D boxes. We prove that it is NP-complete to decide whether a graph admits a proper contact representation by unit cubes. We also describe algorithms that compute proper contact representations of varying size cubes for relevant graph families. Finally, we give two new simple proofs of a theorem by Thomassen stating that all planar graphs have a proper contact representation by touching cuboids. © 2013 Springer-Verlag.
• Das, A., Fleszar, K., Kobourov, S., Spoerhase, J., Veeramoni, S., & Wolff, A. (2013). Approximating the generalized minimum Manhattan network problem. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8283 LNCS, 722-732.
  More info

  Abstract: We consider the generalized minimum Manhattan network problem (GMMN). The input to this problem is a set R of n pairs of terminals, which are points in ℝ2. The goal is to find a minimum-length rectilinear network that connects every pair in R by a Manhattan path, that is, a path of axis-parallel line segments whose total length equals the pair's Manhattan distance. This problem is a natural generalization of the extensively studied minimum Manhattan network problem (MMN) in which R consists of all possible pairs of terminals. Another important special case is the well-known rectilinear Steiner arborescence problem (RSA). As a generalization of these problems, GMMN is NP-hard. No approximation algorithms are known for general GMMN. We obtain an O(logn)-approximation algorithm for GMMN. Our solution is based on a stabbing technique, a novel way of attacking Manhattan network problems. Some parts of our algorithm generalize to higher dimensions, yielding a simple O(log d+1 n)-approximation algorithm for the problem in arbitrary fixed dimension d. As a corollary, we obtain an exponential improvement upon the previously best O(n ε )-ratio for MMN in d dimensions [ESA'11]. En route, we show that an existing O(logn)-approximation algorithm for 2D-RSA generalizes to higher dimensions. © 2013 Springer-Verlag.
• Das, A., Gansner, E. R., Kaufmann, M., Kobourov, S., Spoerhase, J., & Wolff, A. (2013). Approximating Minimum Manhattan Networks in Higher Dimensions. Algorithmica, 1-17.
  More info

  Abstract: We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called terminals in  {Mathematical expression}, find a minimum-length network such that each pair of terminals is connected by a set of axis-parallel line segments whose total length is equal to the pair's Manhattan (that is, L1-) distance. The problem is NP-hard in 2D and there is no PTAS for 3D (unless {Mathematical expression}). Approximation algorithms are known for 2D, but not for 3D. We present, for any fixed dimension d and any ε>0, an O(nε)-approximation algorithm. For 3D, we also give a 4(k-1)-approximation algorithm for the case that the terminals are contained in the union of k≥2 parallel planes. © 2013 Springer Science+Business Media New York.
• Duncan, C. A., Eppstein, D., Goodrich, M. T., Kobourov, S. G., & Nöllenburg, M. (2013). Drawing Trees with Perfect Angular Resolution and Polynomial Area. Discrete and Computational Geometry, 49(2), 157-182.
  More info

  Abstract: We study methods for drawing trees with perfect angular resolution, i. e., with angles at each node v equal to 2π /d(v). We show: 1. Any unordered tree has a crossing-free straight-line drawing with perfect angular resolution and polynomial area. 2. There are ordered trees that require exponential area for any crossing-free straight-line drawing having perfect angular resolution. 3. Any ordered tree has a crossing-free Lombardi-style drawing (where each edge is represented by a circular arc) with perfect angular resolution and polynomial area. Thus, our results explore what is achievable with straight-line drawings and what more is achievable with Lombardi-style drawings, with respect to drawings of trees with perfect angular resolution. © 2012 Springer Science+Business Media New York.
• Evans, W., Felsner, S., Kaufmann, M., Kobourov, S. G., Mondal, D., Nishat, R. I., & Verbeek, K. (2013). Table cartograms. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8125 LNCS, 421-432.
  More info

  Abstract: A table cartogram of a two dimensional m × n table A of non-negative weights in a rectangle R, whose area equals the sum of the weights, is a partition of R into convex quadrilateral faces corresponding to the cells of A such that each face has the same adjacency as its corresponding cell and has area equal to the cell's weight. Such a partition acts as a natural way to visualize table data arising in various fields of research. In this paper, we give a O(mn)-time algorithm to find a table cartogram in a rectangle. We then generalize our algorithm to obtain table cartograms inside arbitrary convex quadrangles, circles, and finally, on the surface of cylinders and spheres. © 2013 Springer-Verlag.
• Fowler, J. J., & Kobourov, S. G. (2013). Planar preprocessing for spring embedders. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7704 LNCS, 388-399.
  More info

  Abstract: Spring embedders are conceptually simple and produce straight-line drawings with an undeniable aesthetic appeal, which explains their prevalence when it comes to automated graph drawing. However, when drawing planar graphs, spring embedders often produce non-plane drawings, as edge crossings do not factor into the objective function being minimized. On the other hand, there are fairly straight-forward algorithms for creating plane straight-line drawings for planar graphs, but the resulting layouts generally are not aesthetically pleasing, as vertices are often grouped in small regions and edges lengths can vary dramatically. It is known that the initial layout influences the output of a spring embedder, and yet a random layout is nearly always the default. We study the effect of using various plane initial drawings as an inputs to a spring embedder, measuring the percent improvement in reducing crossings and in increasing node separation, edge length uniformity, and angular resolution. © 2013 Springer-Verlag.
• Hauser, H., Kobourov, S., & Huamin, Q. u. (2013). Guest Editors' Introduction: Special section on the IEEE Pacific Visualization Symposium 2012. IEEE Transactions on Visualization and Computer Graphics, 19(6), 898-899.
• Hingle, M., Yoon, D., Fowler, J., Kobourov, S., Schneider, M. L., Falk, D., & Burd, R. (2013). Collection and visualization of dietary behavior and reasons for eating using twitter. Journal of Medical Internet Research, 15(6).
  More info

  PMID: 23796439;PMCID: PMC3713881;Abstract: Background: Increasing an individual's awareness and understanding of their dietary habits and reasons for eating may help facilitate positive dietary changes. Mobile technologies allow individuals to record diet-related behavior in real time from any location; however, the most popular software applications lack empirical evidence supporting their efficacy as health promotion tools. Objective: The purpose of this study was to test the feasibility and acceptability of a popular social media software application (Twitter) to capture young adults' dietary behavior and reasons for eating. A secondary aim was to visualize data from Twitter using a novel analytic tool designed to help identify relationships among dietary behaviors, reasons for eating, and contextual factors. Methods: Participants were trained to record all food and beverages consumed over 3 consecutive days (2 weekdays and 1 weekend day) using their mobile device's native Twitter application. A list of 24 hashtags (#) representing food groups and reasons for eating were provided to participants to guide reporting (eg, #protein, #mood). Participants were encouraged to annotate hashtags with contextual information using photos, text, and links. User experience was assessed through a combination of email reports of technical challenges and a 9-item exit survey. Participant data were captured from the public Twitter stream, and frequency of hashtag occurrence and co-occurrence were determined. Contextual data were further parsed and qualitatively analyzed. A frequency matrix was constructed to identify food and behavior hashtags that co-occurred. These relationships were visualized using GMap algorithmic mapping software. Results: A total of 50 adults completed the study. In all, 773 tweets including 2862 hashtags (1756 foods and 1106 reasons for eating) were reported. Frequently reported food groups were #grains (n=365 tweets), #dairy (n=221), and #protein (n=307). The most frequently cited reasons for eating were #social (activity) (n=122), #taste (n=146), and #convenience (n=173). Participants used a combination of study-provided hash tags and their own hash tags to describe behavior. Most rated Twitter as easy to use for the purpose of reporting diet-related behavior. "Maps" of hash tag occurrences and co-occurrences were developed that suggested time-varying diet and behavior patterns. Conclusions: Twitter combined with an analytical software tool provides a method for capturing real-time food consumption and diet-related behavior. Data visualization may provide a method to identify relationships between dietary and behavioral factors. These findings will inform the design of a study exploring the use of social media and data visualization to identify relationships between food consumption, reasons for engaging in specific food-related behaviors, relevant contextual factors, and weight and health statuses in diverse populations.
• Kobourov, S. G., Mondal, D., & Nishat, R. I. (2013). Touching triangle representations for 3-connected planar graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7704 LNCS, 199-210.
  More info

  Abstract: A touching triangle graph (TTG) representation of a planar graph is a planar drawing Γ of the graph, where each vertex is represented as a triangle and each edge e is represented as a side contact of the triangles that correspond to the end vertices of e. We call Γ a proper TTG representation if Γ determines a tiling of a triangle, where each tile corresponds to a distinct vertex of the input graph. In this paper we prove that every 3-connected cubic planar graph admits a proper TTG representation. We also construct proper TTG representations for parabolic grid graphs and the graphs determined by rectangular grid drawings (e.g., square grid graphs). Finally, we describe a fixed-parameter tractable decision algorithm for testing whether a 3-connected planar graph admits a proper TTG representation. © 2013 Springer-Verlag.
• Kobourov, S., Ueckerdt, T., & Verbeek, K. (2013). Combinatorial and geometric properties of planar Laman graphs. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 1668-1678.
  More info

  Abstract: Laman graphs naturally arise in structural mechanics and rigidity theory. Specifically, they characterize minimally rigid planar bar-and-joint systems which are frequently needed in robotics, as well as in molecular chemistry and polymer physics. We introduce three new combinatorial structures for planar Laman graphs: angular structures, angle labelings, and edge labelings. The latter two structures are related to Schnyder realizers for maximally planar graphs. We prove that planar Laman graphs are exactly the class of graphs that have an angular structure that is a tree, called angular tree, and that every angular tree has a corresponding angle labeling and edge labeling. Using a combination of these powerful combinatorial structures, we show that every planar Laman graph has an L-contact representation, that is, planar Laman graphs are contact graphs of axis-aligned L-shapes. Moreover, we show that planar Laman graphs and their subgraphs are the only graphs that can be represented this way. We present efficient algorithms that compute, for every planar Laman graph G, an angular tree, angle labeling, edge labeling, and finally an L-contact representation of G. The overall running time is Script O sign(n 2), where n is the number of vertices of G, and the L-contact representation is realized on the n x n grid. Copyright © SIAM.
• Kämper, J., Kobourov, S. G., & Nollenburg, M. (2013). Circular-arc cartograms. IEEE Pacific Visualization Symposium, 1-8.
  More info

  Abstract: We present a new circular-arc cartogram model in which countries are drawn as polygons with circular arcs instead of straight-line segments. Given a political map and values associated with each country in the map, a cartogram is a distorted map in which the areas of the countries are proportional to the corresponding values. In the circular-arc cartogram model straight-line segments can be replaced by circular arcs in order to modify the areas of the polygons, while the corners of the polygons remain fixed. The countries in circular-arc cartograms have the aesthetically pleasing appearance of clouds or snowflakes, depending on whether their edges are bent outwards or inwards. This makes it easy to determine whether a country has grown or shrunk, just by its overall shape. We show that determining whether a given map and given area-values can be realized as a circular-arc cartogram is an NP-hard problem. Next we describe a heuristic method for constructing circular-arc cartograms, which uses a max-flow computation on the dual graph of the map, along with a computation of the straight skeleton of the underlying polygonal decomposition. Our method is implemented and produces cartograms that, while not yet perfectly accurate, achieve many of the desired areas in our real-world examples. © 2013 IEEE.
• Purchase, H. C., Hamer, J., Nöllenburg, M., & Kobourov, S. G. (2013). On the usability of Lombardi graph drawings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7704 LNCS, 451-462.
  More info

  Abstract: A recent line of work in graph drawing studies Lombardi drawings, i.e., drawings with circular-arc edges and perfect angular resolution at vertices. Little is known about the effects of curved edges versus straight edges in typical graph reading tasks. In this paper we present the first user evaluation that empirically measures the readability of three different layout algorithms (traditional spring embedder and two recent near-Lombardi force-based algorithms) for three different tasks (shortest path, common neighbor, vertex degree). The results indicate that, while users prefer the Lombardi drawings, the performance data do not present such a positive picture. © 2013 Springer-Verlag.
• Alam, M. J., Biedl, T., Felsner, S., Kaufmann, M., & Kobourov, S. G. (2012). Proportional contact representations of planar graphs. Journal of Graph Algorithms and Applications, 16(3), 701-728.
  More info

  Abstract: We study contact representations for planar graphs, with vertices rep- resented by simple polygons and adjacencies represented by point-contacts or side-contacts between the corresponding polygons. Specifically, we consider proportional contact representations, where pre-specified vertex weights must be represented by the areas of the corresponding polygons. Natural optimization goals for such representations include minimizing the complexity of the polygons, and the unused area. We describe al- gorithms for proportional contact representations with optimal polygonal complexity for general planar graphs and planar 2-segment graphs, which include maximal outer-planar graphs and partial 2-trees.
• Alam, M. J., Biedl, T., Felsner, S., Kaufmann, M., & Kobourov, S. G. (2012). Proportional contact representations of planar graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7034 LNCS, 26-38.
  More info

  Abstract: We study contact representations for planar graphs, with vertices represented by simple polygons and adjacencies represented by point-contacts or side-contacts between the corresponding polygons. Specifically, we consider proportional contact representations, where pre-specified vertex weights must be represented by the areas of the corresponding polygons. Several natural optimization goals for such representations include minimizing the complexity of the polygons, the cartographic error, and the unused area. We describe constructive algorithms for proportional contact representations with optimal complexity for general planar graphs and planar 2-segment graphs, which include maximal outerplanar graphs and partial 2-trees. © 2012 Springer-Verlag Berlin Heidelberg.
• Alam, M. J., Biedl, T., Felsner, S., Kaufmann, M., Kobourov, S. G., & Ueckerdt, T. (2012). Computing cartograms with optimal complexity. Proceedings of the Annual Symposium on Computational Geometry, 21-30.
  More info

  Abstract: In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by side-contact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a pre-specified weight. The complexity of a cartogram is determined by the maximum number of corners (or sides) required for any polygon. In a series of papers the polygonal complexity of such representations for maximal planar graphs has been reduced from the initial 40 to 34, then to 12 and very recently to the currently best known 10. Here we describe a construction with 8-sided polygons, which is optimal in terms of polygonal complexity as 8-sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an area-universal rectangular layout in linear time. The exact cartogram can be computed from the area-universal layout with numerical iteration, or can be approximated with a hill-climbing heuristic. We also describe an alternative construction of cartograms for Hamiltonian maximal planar graphs, which allows us to directly compute the cartograms in linear time. Moreover, we prove that even for Hamiltonian graphs 8-sided rectilinear polygons are necessary, by constructing a non-trivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is one-legged, as in outer-planar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outer-planar graphs. Copyright © 2012 ACM.
• Angelini, P., Didimo, W., Kobourov, S., McHedlidze, T., Roselli, V., Symvonis, A., & Wismath, S. (2012). Monotone drawings of graphs with fixed embedding. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7034 LNCS, 379-390.
  More info

  Abstract: A drawing of a graph is a monotone drawing if for every pair of vertices u and v, there is a path drawn from u to v that is monotone in some direction. In this paper we investigate planar monotone drawings in the fixed embedding setting, i.e., a planar embedding of the graph is given as part of the input that must be preserved by the drawing algorithm. In this setting we prove that every planar graph on n vertices admits a planar monotone drawing with at most two bends per edge and with at most 4n - 10 bends in total; such a drawing can be computed in linear time and requires polynomial area. We also show that two bends per edge are sometimes necessary on a linear number of edges of the graph. Furthermore, we investigate subclasses of planar graphs that can be realized as embedding-preserving monotone drawings with straight-line edges, and we show that biconnected embedded planar graphs and outerplane graphs always admit such drawings, which can be computed in linear time. © 2012 Springer-Verlag Berlin Heidelberg.
• Chernobelskiy, R., Cunningham, K. I., Goodrich, M. T., Kobourov, S. G., & Trott, L. (2012). Force-directed Lombardi-style graph drawing. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7034 LNCS, 320-331.
  More info

  Abstract: A Lombardi drawing of a graph is one in which vertices are represented as points, edges are represented as circular arcs between their endpoints, and every vertex has perfect angular resolution (equal angles between consecutive edges, as measured by the tangents to the circular arcs at the vertex). We describe two algorithms that create "Lombardi-style" drawings (which we also call near-Lombardi drawings), in which all edges are still circular arcs, but some vertices may not have perfect angular resolution. Both of these algorithms take a force-directed, spring-embedding approach, with one using forces at edge tangents to produce curved edges and the other using dummy vertices on edges for this purpose. As we show, these approaches produce near-Lombardi drawings, with one being slightly better at achieving near-perfect angular resolution and the other being slightly better at balancing edge placements. © 2012 Springer-Verlag Berlin Heidelberg.
• Duncan, C. A., Eppstein, D., Goodrich, M. T., Kobourov, S. G., & Löffler, M. (2012). Planar and poly-arc Lombardi drawings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7034 LNCS, 308-319.
  More info

  Abstract: In Lombardi drawings of graphs, edges are represented as circular arcs, and the edges incident on vertices have perfect angular resolution. However, not every graph has a Lombardi drawing, and not every planar graph has a planar Lombardi drawing. We introduce k-Lombardi drawings, in which each edge may be drawn with k circular arcs, noting that every graph has a smooth 2-Lombardi drawing. We show that every planar graph has a smooth planar 3-Lombardi drawing and further investigate topics connecting planarity and Lombardi drawings. © 2012 Springer-Verlag Berlin Heidelberg.
• Duncan, C. A., Eppstein, D., Goodrich, M. T., Kobourov, S. G., & Nöllenburg, M. (2012). Lombardi drawings of graphs. Journal of Graph Algorithms and Applications, 16(1), 85-108.
  More info

  Abstract: We introduce the notion of Lombardi graph drawings, named after the American abstract artist Mark Lombardi. In these drawings, edges are represented as circular arcs rather than as line segments or polylines, and the vertices have perfect angular resolution: the edges are equiangularly spaced around each vertex. We describe algorithms for _nding Lombardi drawings of regular graphs, graphs of bounded degeneracy, and certain families of planar graphs.
• Hauser, H., Kobourov, S., & Huamin, Q. u. (2012). A message from the program chairs. IEEE Pacific Visualization Symposium 2012, PacificVis 2012 - Proceedings, vi.
• Mashima, D., Kobourov, S., & Yifan, H. u. (2012). Visualizing dynamic data with maps. IEEE Transactions on Visualization and Computer Graphics, 18(9), 1424-1437.
  More info

  Abstract: Maps offer a familiar way to present geographic data (continents, countries), and additional information (topography, geology), can be displayed with the help of contours and heat-map overlays. In this paper, we consider visualizing large-scale dynamic relational data by taking advantage of the geographic map metaphor. We describe a map-based visualization system which uses animation to convey dynamics in large data sets, and which aims to preserve the viewer's mental map while also offering readable views at all times. Our system is fully functional and has been used to visualize user traffic on the Internet radio station last.fm, as well as TV-viewing patterns from an IPTV service. All map images in this paper are available in high-resolution at [1] as are several movies illustrating the dynamic visualization. © 2012 IEEE.
• Yifan, H. u., Kobourov, S. G., & Veeramoni, S. (2012). Embedding, clustering and coloring for dynamic maps. IEEE Pacific Visualization Symposium 2012, PacificVis 2012 - Proceedings, 33-40.
  More info

  Abstract: We describe a practical approach for visualizing multiple relationships defined on the same dataset using a geographic map metaphor, where clusters of nodes form countries and neighboring countries correspond to nearby clusters. Our aim is to provide a visualization that allows us to compare two or more such maps (showing an evolving dynamic process, or obtained using different relationships). In the case where we are considering multiple relationships, e.g., different similarity metrics, we also provide an interactive tool to visually explore the effect of combining two or more such relationships. Our method ensures good readability and mental map preservation, based on dynamic node placement with node stability, dynamic clustering with cluster stability, and dynamic coloring with color stability. © 2012 IEEE.
• Alam, M. J., Biedl, T., Felsner, S., Gerasch, A., Kaufmann, M., & Kobourov, S. G. (2011). Linear-time algorithms for hole-free rectilinear proportional contact graph representations. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7074 LNCS, 281-291.
  More info

  Abstract: In a proportional contact representation of a planar graph, each vertex is represented by a simple polygon with area proportional to a given weight, and edges are represented by adjacencies between the corresponding pairs of polygons. In this paper we study proportional contact representations that use rectilinear polygons without wasted areas (white space). In this setting, the best known algorithm for proportional contact representation of a maximal planar graph uses 12-sided rectilinear polygons and takes O(nlogn) time. We describe a new algorithm that guarantees 10-sided rectilinear polygons and runs in O(n) time. We also describe a linear-time algorithm for proportional contact representation of planar 3-trees with 8-sided rectilinear polygons and show that this is optimal, as there exist planar 3-trees that require 8-sided polygons. Finally, we show that a maximal outer-planar graph admits a proportional contact representation using rectilinear polygons with 6 sides when the outer-boundary is a rectangle and with 4 sides otherwise. © 2011 Springer-Verlag.
• Biedl, T., Dernaine, E., Duncan, C., Fleischer, R., & Kobourov, S. (2011). Tight bounds on maximal and maximum matchings. DISCRETE MATHEMATICS, 285(1-3), 7-15.
  More info

  In this paper, we study lower bounds on the size of maximal and maximum matchings in 3-connected planar graphs and graphs with bounded maximum degree. For each class, we give a lower bound on the size of matchings, and show that the bound is tight for some graph within the class. (C) 2004 Elsevier B.V. All rights reserved.
• Brandes, U., Erten, C., Estrella-Balderrama, A., Fowler, J. J., Frati, F., Geyer, M., Gutwenger, C., Hong, S., Kaufmann, M., Kobourov, S. G., Liotta, G., Mutzel, P., & Symvonis, A. (2011). Colored simultaneous geometric embeddings and universal pointsets. Algorithmica (New York), 60(3), 569-592.
  More info

  Abstract: Universal pointsets can be used for visualizing multiple relationships on the same set of objects or for visualizing dynamic graph processes. In simultaneous geometric embeddings, the same point in the plane is used to represent the same object as a way to preserve the viewer's mental map. In colored simultaneous embeddings this restriction is relaxed, by allowing a given object to map to a subset of points in the plane. Specifically, consider a set of graphs on the same set of n vertices partitioned into k colors. Finding a corresponding set of k-colored points in the plane such that each vertex is mapped to a point of the same color so as to allow a straightline plane drawing of each graph is the problem of colored simultaneous geometric embedding. © Springer Science+Business Media, LLC 2009.
• Das, A., Gansner, E. R., Kaufmann, M., Kobourov, S., Spoerhase, J., & Wolff, A. (2011). Approximating minimum manhattan networks in higher dimensions. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6942 LNCS, 49-60.
  More info

  Abstract: We consider the minimum Manhattan network problem, which is defined as follows. Given a set of points called terminals in ℝd , find a minimum-length network such that each pair of terminals is connected by a set of axis-parallel line segments whose total length is equal to the pair's Manhattan (that is, L 1-) distance. The problem is NP-hard in 2D and there is no PTAS for 3D (unless P=NP ). Approximation algorithms are known for 2D, but not for 3D. We present, for any fixed dimension d and any ε O, an O(n ε-approximation. For 3D, we also give a 4(k-1)-approximation for the case that the terminals are contained in the union of κ≥2 parallel planes. © 2011 Springer-Verlag Berlin Heidelberg.
• Dujmović, V., Evans, W., Kobourov, S., Liotta, G., Weibel, C., & Wismath, S. (2011). On graphs supported by line sets. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6502 LNCS, 177-182.
  More info

  Abstract: For a set S of n lines labeled from 1 to n, we say that S supports an n-vertex planar graph G if for every labeling from 1 to n of its vertices, G has a straight-line crossing-free drawing with each vertex drawn as a point on its associated line. It is known from previous work [4] that no set of n parallel lines supports all n-vertex planar graphs. We show that intersecting lines, even if they intersect at a common point, are more "powerful" than a set of parallel lines. In particular, we prove that every such set of lines supports outerpaths, lobsters, and squids, none of which are supported by any set of parallel lines. On the negative side, we prove that no set of n lines that intersect in a common point supports all n-vertex planar graphs. Finally, we show that there exists a set of n lines in general position that does not support all n-vertex planar graphs. © 2011 Springer-Verlag.
• Duncan, C. A., Eppstein, D., Goodrich, M. T., Kobourov, S. G., & Nöllenburg, M. (2011). Drawing trees with perfect angular resolution and polynomial area. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6502 LNCS, 183-194.
  More info

  Abstract: We study methods for drawing trees with perfect angular resolution, i.e., with angles at each vertex, v, equal to 2π/d(v). We show: 1 Any unordered tree has a crossing-free straight-line drawing with perfect angular resolution and polynomial area. 2 There are ordered trees that require exponential area for any crossing-free straight-line drawing having perfect angular resolution. 3 Any ordered tree has a crossing-free Lombardi-style drawing (where each edge is represented by a circular arc) with perfect angular resolution and polynomial area. Thus, our results explore what is achievable with straight-line drawings and what more is achievable with Lombardi-style drawings, with respect to drawings of trees with perfect angular resolution. © 2011 Springer-Verlag.
• Duncan, C. A., Eppstein, D., Goodrich, M. T., Kobourov, S. G., & Nöllenburg, M. (2011). Lombardi drawings of graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6502 LNCS, 195-207.
  More info

  Abstract: We introduce the notion of Lombardi graph drawings, named after the American abstract artist Mark Lombardi. In these drawings, edges are represented as circular arcs rather than as line segments or polylines, and the vertices have perfect angular resolution: the edges are equally spaced around each vertex. We describe algorithms for finding Lombardi drawings of regular graphs, graphs of bounded degeneracy, and certain families of planar graphs. © 2011 Springer-Verlag.
• Duncan, C. A., Gansner, E. R., Hu, Y. F., Kaufmann, M., & Kobourov, S. G. (2011). Optimal Polygonal Representation of Planar Graphs. Algorithmica (New York), 1-20.
  More info

  Abstract: In this paper, we consider the problem of representing planar graphs by polygons whose sides touch. We show that at least six sides per polygon are necessary by constructing a class of planar graphs that cannot be represented by pentagons. We also show that the lower bound of six sides is matched by an upper bound of six sides with a linear-time algorithm for representing any planar graph by touching hexagons. Moreover, our algorithm produces convex polygons with edges having at most three slopes and with all vertices lying on an O(n)×O(n) grid. © 2011 Springer Science+Business Media, LLC.
• Duncan, C. A., Goodrich, M. T., & Kobourov, S. G. (2011). Planar drawings of higher-genus graphs. Journal of Graph Algorithms and Applications, 15(1), 7-32.
  More info

  Abstract: In this paper, we give polynomial-time algorithms that can take a graph G with a given combinatorial embedding on an orientable surface S of genus g and produce a planar drawing of G in R 2, with a bounding face dened by a polygonal schema P for S. Our drawings are planar, but they allow for multiple copies of vertices and edges on P's boundary, which is a common way of visualizing higher-genus graphs in the plane. However, unlike traditional approaches the copies of the vertices might not be in perfect alignment but we guarantee that their order along the boundary is still preserved. Our drawings can be dened with respect to either a canonical polygonal schema or a polygonal cutset schema, which provides an interesting tradeo, since canonical schemas have fewer sides, and have a nice topological structure, but they can have many more repeated vertices and edges than general polygonal cutsets. As a side note, we show that it is NP-complete to determine whether a given graph embedded in a genus-g surface has a set of 2g fundamental cycles with vertex-disjoint interiors, which would be desirable from a graph-drawing perspective.
• Fowler, J. J., Jünger, M., Kobourov, S. G., & Schulz, M. (2011). Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges. Computational Geometry: Theory and Applications, 44(8), 385-398.
  More info

  Abstract: A set of planar graphs {G1(V,E1),⋯, Gk(V,Ek)} admits a simultaneous embedding if they can be drawn on the same pointset P of order n in the Euclidean plane such that each point in P corresponds one-to-one to a vertex in V and each edge in Ei does not cross any other edge in Ei (except at endpoints) for i∈{1,⋯,k}. A fixed edge is an edge (u,v) that is drawn using the same simple curve for each graph Gi whose edge set Ei contains the edge (u,v). We give a necessary and sufficient condition for two graphs whose union is homeomorphic to K5 or K3 ,3 to admit a simultaneous embedding with fixed edges (SEFE). This allows us to characterize the class of planar graphs that always have a SEFE with any other planar graph. We also characterize the class of biconnected outerplanar graphs that always have a SEFE with any other outerplanar graph. In both cases, we provide O(n4)-time algorithms to compute a SEFE. © 2011 Elsevier B.V.
• Gansner, E. R., Yifan, H. u., & Kobourov, S. G. (2011). On touching triangle graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6502 LNCS, 250-261.
  More info

  Abstract: In this paper, we consider the problem of representing graphs by triangles whose sides touch. We present linear time algorithms for creating touching triangles representations for outerplanar graphs, square grid graphs, and hexagonal grid graphs. The class of graphs with touching triangles representations is not closed under minors, making characterization difficult. We do show that pairs of vertices can only have a small common neighborhood, and we present a complete characterization of the subclass of biconnected graphs that can be represented as triangulations of some polygon. © 2011 Springer-Verlag.
• Isaacman, S., Becker, R., Caceres, R., Kobourov, S., Martonosi, M., Rowland, J., & Varshavsky, A. (2011). Ranges of human mobility in Los Angeles and New York. 2011 IEEE International Conference on Pervasive Computing and Communications Workshops, PERCOM Workshops 2011, 88-93.
  More info

  Abstract: The advent of ubiquitous, mobile, personal devices creates an unprecedented opportunity to improve our understanding of human movement. In this work, we study human mobility in Los Angeles and New York by analyzing anonymous records of approximate locations of cell phones belonging to residents of those cities. We examine two data sets gathered six months apart, each representing hundreds of thousands of people, containing hundreds of millions of location events, and spanning two months of activity. We present, compare, and validate the daily range of travel for people in these populations. Our findings include that human mobility changes with the seasons: both Angelenos and New Yorkers travel less in the winter, with New Yorkers showing a greater decrease in mobility during the cold months. We also show that text messaging activity does not by itself accurately characterize daily range, whereas voice calling alone suffices. Finally, we show that our methodology is accurate by comparing our results to ground truth obtained from volunteers. © 2011 IEEE.
• Isaacman, S., Becker, R., Cáceres, R., Kobourov, S., Martonosi, M., Rowland, J., & Varshavsky, A. (2011). Identifying important places in people's lives from cellular network data. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6696 LNCS, 133-151.
  More info

  Abstract: People spend most of their time at a few key locations, such as home and work. Being able to identify how the movements of people cluster around these "important places" is crucial for a range of technology and policy decisions in areas such as telecommunications and transportation infrastructure deployment. In this paper, we propose new techniques based on clustering and regression for analyzing anonymized cellular network data to identify generally important locations, and to discern semantically meaningful locations such as home and work. Starting with temporally sparse and spatially coarse location information, we propose a new algorithm to identify important locations. We test this algorithm on arbitrary cellphone users, including those with low call rates, and find that we are within 3 miles of ground truth for 88% of volunteer users. Further, after locating home and work, we achieve commute distance estimates that are within 1 mile of equivalent estimates derived from government census data. Finally, we perform carbon footprint analyses on hundreds of thousands of anonymous users as an example of how our data and algorithms can form an accurate and efficient underpinning for policy and infrastructure studies. © 2011 Springer-Verlag.
• Mashima, D., Kobourov, S. G., & Yifan, H. u. (2011). Visualizing dynamic data with maps. IEEE Pacific Visualization Symposium 2011, PacificVis 2011 - Proceedings, 155-162.
  More info

  Abstract: Maps offer a familiar way to present geographic data (continents, countries), and additional information (topography, geology), can be displayed with the help of contours and heat-map overlays. In this paper we consider visualizing large-scale dynamic relational data by taking advantage of the geographic map metaphor. We describe a system that visualizes user traffic on the Internet radio station last.fm and address challenges in mental map preservation, as well as issues in animated map-based visualization. 12 © 2011 IEEE.
• Yifan, H. u., Kobourov, S., & Veeramoni, S. (2011). On maximum differential graph coloring. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6502 LNCS, 274-286.
  More info

  Abstract: We study the maximum differential graph coloring problem, in which the goal is to find a vertex labeling for a given undirected graph that maximizes the label difference along the edges. This problem has its origin in map coloring, where not all countries are necessarily contiguous. We define the differential chromatic number and establish the equivalence of the maximum differential coloring problem to that of k-Hamiltonian path. As computing the maximum differential coloring is NP-Complete, we describe an exact backtracking algorithm and a spectral-based heuristic. We also discuss lower bounds and upper bounds for the differential chromatic number for several classes of graphs. © 2011 Springer-Verlag.
• Binucci, C., Di Giacomo, E., Didimo, W., Estrella-Balderrama, A., Frati, F., Kobourov, S. G., & Liotta, G. (2010). Upward straight-line embeddings of directed graphs into point sets. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 43(2), 219-232.
  More info

  In this paper we study the problem of computing an upward straight-line embedding of a planar DAG (directed acyclic graph) G into a point set S, i.e. a planar drawing of G such that each vertex is mapped to a point of S, each edge is drawn as a straight-line segment, and all the edges are oriented according to a common direction. In particular, we show that no biconnected DAG admits an upward straight-line embedding into every point set in convex position. We provide a characterization of the family of DAGs that admit an upward straight-line embedding into every convex point set such that the points with the largest and the smallest y-coordinate are consecutive in the convex hull of the point set. We characterize the family of DAGs that contain a Hamiltonian directed path and that admit an upward straight-line embedding into every point set in general position. We also prove that a DAG whose underlying graph is a tree does not always have an upward straight-line embedding into a point set in convex position and we describe how to construct such an embedding for a DAG whose underlying graph is a path. Finally, we give results about the embeddability of some sub-classes of DAGs whose underlying graphs are trees on point set in convex and in general position. (C) 2009 Elsevier B.V. All rights reserved
• Binucci, C., Giacomo, E. D., Didimo, W., Estrella-Balderrama, A., Frati, F., Kobourov, S. G., & Liotta, G. (2010). Upward straight-line embeddings of directed graphs into point sets. Computational Geometry: Theory and Applications, 43(2 SPEC. ISS.), 219-232.
  More info

  Abstract: In this paper we study the problem of computing an upward straight-line embedding of a planar DAG (directed acyclic graph) G into a point set S, i.e. a planar drawing of G such that each vertex is mapped to a point of S, each edge is drawn as a straight-line segment, and all the edges are oriented according to a common direction. In particular, we show that no biconnected DAG admits an upward straight-line embedding into every point set in convex position. We provide a characterization of the family of DAGs that admit an upward straight-line embedding into every convex point set such that the points with the largest and the smallest y-coordinate are consecutive in the convex hull of the point set. We characterize the family of DAGs that contain a Hamiltonian directed path and that admit an upward straight-line embedding into every point set in general position. We also prove that a DAG whose underlying graph is a tree does not always have an upward straight-line embedding into a point set in convex position and we describe how to construct such an embedding for a DAG whose underlying graph is a path. Finally, we give results about the embeddability of some sub-classes of DAGs whose underlying graphs are trees on point set in convex and in general position. © 2009 Elsevier B.V. All rights reserved.
• Coogan, K., Khare, V., Kobourov, S. G., & Katz, B. (2010). MSDR-D network localization algorithm. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6451 LNCS, 148-160.
  More info

  Abstract: We present a distributed multi-scale dead-reckoning (MSDR-D) algorithm for network localization that utilizes local distance and angular information for nearby sensors. The algorithm is anchor-free and does not require particular network topology, rigidity of the underlying communication graph, or high average connectivity. The algorithm scales well to large and sparse networks with complex topologies and outperforms previous algorithms when the noise levels are high. The algorithm is simple to implement and is available, along with source code, executables, and experimental results, at http://msdr-d.cs. arizona.edu/. © 2010 Springer-Verlag.
• Duncan, C. A., Goodrich, M. T., & Kobourov, S. G. (2010). Planar drawings of higher-genus graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5849 LNCS, 45-56.
  More info

  Abstract: In this paper, we give polynomial-time algorithms that can take a graph G with a given combinatorial embedding on an orientable surface of genus g and produce a planar drawing of G in R2, with a bounding face defined by a polygonal schema for P for S. Our drawings are planar, but they allow for multiple copies of vertices and edges on 's boundary, which is a common way of visualizing higher-genus graphs in the plane. As a side note, we show that it is NP-complete to determine whether a given graph embedded in a genus-g surface has a set of 2g fundamental cycles with vertex-disjoint interiors, which would be desirable from a graph-drawing perspective. © 2010 Springer-Verlag.
• Erten, C., Kobourov, S., Le, ., Navabi, A., & Liotta, G. (2010). Simultaneous graph drawing: Layout algorithms and visualization schemes. GRAPH DRAWING, 2912, 437-449.
  More info

  In this paper we consider the problem of drawing and displaying a series of related graphs, i.e., graphs that share all, or parts of the same vertex set. We designed and implemented three different algorithms for simultaneous graph drawing and three different visualization schemes. The algorithms are based on a modification of the force-directed algorithm that allows us to take into account vertex weights and edge weights in order to achieve mental map preservation while obtaining individually readable drawings.
• Estrella-Balderrama, A., Fowler, J. J., & Kobourov, S. G. (2010). GraphSET, a tool for simultaneous graph drawing. Software - Practice and Experience, 40(10), 849-863.
  More info

  Abstract: Problems in simultaneous graph drawing involve the layout of several graphs on a shared vertex set. This paper describes a Graph Simultaneous Embedding Tool, GraphSET, designed to allow the investigation of a wide range of graph embedding problems. GraphSET can be used in the study of several variants of simultaneous embedding including simultaneous geometric embedding, simultaneous embedding with fixed edges, and colored simultaneous embedding with the vertex set partitioned into color classes. The tool has three primary uses: (i) studying theoretical problems in simultaneous graph drawing through the production of examples and counterexamples, (ii) producing layouts of given classes of graphs using built-in implementations of known algorithms, and (iii) providing a platform for development and implementation of new algorithms and data structures for all variants of simultaneous graph embedding. We also describe the design decisions involved in the construction of GraphSET in terms of the requirements dictated by its applications. GraphSET along with movies illustrating its utility are available at http://graphset.cs.arizona.edu. Copyright © 2010 John Wiley & Sons, Ltd.
• Estrella-Balderrama, A., Fowler, J. J., & Kobourov, S. G. (2010). On the characterization of level planar trees by minimal patterns. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5849 LNCS, 69-80.
  More info

  Abstract: We consider characterizations of level planar trees. Healy et al. [8] characterized the set of trees that are level planar in terms of two minimal level non-planar (MLNP) patterns. Fowler and Kobourov [7] later proved that the set of patterns was incomplete and added two additional patterns. In this paper, we show that the characterization is still incomplete by providing new MLNP patterns not included in the previous characterizations. Moreover, we introduce an iterative method to create an arbitrary number of MLNP patterns, thus proving that the set of minimal patterns that characterizes level planar trees is infinite. © 2010 Springer-Verlag.
• Gansner, E. R., Hu, Y. F., Kaufmann, M., & Kobourov, S. G. (2010). Optimal polygonal representation of planar graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6034 LNCS, 417-432.
  More info

  Abstract: In this paper, we consider the problem of representing graphs by polygons whose sides touch. We show that at least six sides per polygon are necessary by constructing a class of planar graphs that cannot be represented by pentagons. We also show that the lower bound of six sides is matched by an upper bound of six sides with a linear time algorithm for representing any planar graph by touching hexagons. Moreover, our algorithm produces convex polygons with edges with slopes 0, 1, -1. © 2010 Springer-Verlag.
• Gansner, E. R., Yifan, H. u., & Kobourov, S. (2010). GMap: Visualizing graphs and clusters as maps. IEEE Pacific Visualization Symposium 2010, PacificVis 2010 - Proceedings, 201-208.
  More info

  Abstract: Information visualization is essential in making sense out of large data sets. Often, high-dimensional data are visualized as a collection of points in 2-dimensional space through dimensionality reduction techniques. However, these traditional methods often do not capture well the underlying structural information, clustering, and neighborhoods. In this paper, we describe GMap, a practical algorithm for visualizing relational data with geographic-like maps. We illustrate the effectiveness of this approach with examples from several domains. ©2010 IEEE.
• Gansner, E. R., Yifan, H. u., & Kobourov, S. G. (2010). GMap: Drawing graphs as maps. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5849 LNCS, 405-407.
• Isaacman, S., Becker, R., Cáceres, R., Kobourov, S., Rowland, J., & Varshavsky, A. (2010). A tale of two cities. HotMobile 2010: The 11th Workshop on Mobile Computing Systems and Applications, 19-24.
  More info

  Abstract: An improved understanding of human mobility patterns would yield insights into a variety of important societal issues such as the environmental impact of daily commutes. Location information from cellular wireless networks has great potential as a tool for studying these patterns. In this work, we use anonymous and aggregate statistics of the approximate locations of hundreds of thousands of cell phones in Los Angeles and New York City to demonstrate different mobility patterns in the two cities. For example, we show that Angelenos have median daily travel distances two times greater than New Yorkers, but that the most mobile 25% of New Yorkers travel six times farther than their Los Angeles counterparts. Copyright 2010 ACM.
• Yifan, H. u., Gansner, E. R., & Kobourov, S. (2010). Visualizing graphs and clusters as maps. IEEE Computer Graphics and Applications, 30(6), 54-66.
  More info

  Abstract: Information visualization is essential in making sense of large datasets. Often, high-dimensional data are visualized as a collection of points in 2D space through dimensionality reduction techniques. However, these traditional methods often don't capture the underlying structural information, clustering, and neighborhoods well. GMap is a practical algorithmic framework for visualizing relational data with geographic-like maps. This approach is effective in various domains. © 2006 IEEE.
• Alam, M. J., Chaplick, S., Fijavž, G., Kaufmann, M., Kobourov, S. G., & Pupyrev, S. (2009). Threshold-coloring and unit-cube contact representation of graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8165 LNCS, 26-37.
  More info

  Abstract: We study threshold coloring of graphs where the vertex colors, represented by integers, describe any spanning subgraph of the given graph as follows. Pairs of vertices with near colors imply the edge between them is present and pairs of vertices with far colors imply the edge is absent. Not all planar graphs are threshold-colorable, but several subclasses, such as trees, some planar grids, and planar graphs with no short cycles can always be threshold-colored. Using these results we obtain unit-cube contact representation of several subclasses of planar graphs. We show the NP-completeness for two variants of the threshold coloring problem and describe a polynomial-time algorithm for another. © 2013 Springer-Verlag.
• Binucci, C., Giacomo, E. D., Didimo, W., Estrella-Balderrama, A., Frati, F., Kobourov, S. G., & Liotta, G. (2009). On directed graphs with an upward straight-line embedding into every point set. Proceedings of the 21st Annual Canadian Conference on Computational Geometry, CCCG 2009, 21-24.
  More info

  Abstract: In this paper we study the problem of computing an up- ward straight-line embedding of a directed graph G into a point set S, i.e. a planar drawing of G such that each vertex is mapped to a point of S, each edge is drawn as a straight-line segment, and all the edges are oriented according to a common direction. We characterize the family of directed graphs that admit an upward straight-line embedding into every one-side convex point set, that is, into every point-set such that the top-most and the bottom-most points are adjacent in the convex hull of the point set. Also we show how to construct up- ward straight-line embeddings for a sub-class of directed paths when the point set is in general position.
• Cappos, J., Estrella-Balderrama, A., Fowler, J. J., & Kobourov, S. G. (2009). Simultaneous graph embedding with bends and circular arcs. Computational Geometry: Theory and Applications, 42(2), 173-182.
  More info

  Abstract: A simultaneous embedding of two vertex-labeled planar graphs on n vertices is possible if there exists a labeled point set of size n such that each of the graphs can be realized on that point set without crossings. We demonstrate how to simultaneously embed a path and an n-level planar graph and how to use radial embeddings for curvilinear simultaneous embeddings of a path and an outerplanar graph. We also show how to use star-shaped levels to find 2-bends per path edge simultaneous embeddings of a path and an outerplanar graph. All embedding algorithms run in O(n) time. © 2008 Elsevier B.V.
• Chaplick, S., Kobourov, S. G., & Ueckerdt, T. (2009). Equilateral L-contact graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8165 LNCS, 139-151.
  More info

  Abstract: We consider L-graphs, that is contact graphs of axis-aligned L-shapes in the plane, all with the same rotation. We provide several characterizations of L-graphs, drawing connections to Schnyder realizers and canonical orders of maximally planar graphs. We show that every contact system of L's can always be converted to an equivalent one with equilateral L's. This can be used to show a stronger version of a result of Thomassen, namely, that every planar graph can be represented as a contact system of square-based cuboids. We also study a slightly more restricted version of equilateral L-contact systems and show that these are equivalent to homothetic triangle contact representations of maximally planar graphs. We believe that this new interpretation of the problem might allow for efficient algorithms to find homothetic triangle contact representations, that do not use Schramm's monster packing theorem. © 2013 Springer-Verlag.
• Duncan, C., Goodrich, M., & Kobourov, S. (2009). Balanced aspect ratio trees: Combining the advantages of k-d trees and octrees. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 38(1), 303-333.
  More info

  Given a set S of n points on R(d), we show, for fixed Li, how to construct in O(n log n) time a data structure we call the balanced aspect ratio (BAR) tree. A BAR tree is a binary space partition tree on S that has O(log n) depth in which every region is convex and "fat" (that is, has a bounded aspect ratio). While previous hierarchical data structures such as k-d trees, quadtrees, octrees, fair-split trees, and balanced box decompositions can guarantee some of these properties, we know of no previous data structure that combines all of these properties simultaneously. The BAR tree data structure has numerous applications ranging from geometric searching problems in fixed dimensional space to the visualization of graphs and three-dimensional worlds, (C) 2001 Academic Press.
• Estrella-Balderrama, A., Fowler, J. J., & Kobourov, S. G. (2009). Characterization of unlabeled level planar trees. Computational Geometry: Theory and Applications, 42(6-7), 704-721.
  More info

  Abstract: Consider a graph G with vertex set V in which each of the n vertices is assigned a number from the set {1,...,k} for some positive integer k. This assignment φ is a labeling if all k numbers are used. If φ does not assign adjacent vertices the same label, then φ forms a leveling that partitions V into k levels. If G has a planar drawing in which the y-coordinate of all vertices match their labels and edges are drawn strictly y-monotone, then G is level planar. In this paper, we consider the class of level trees that are level planar regardless of their labeling. We call such trees unlabeled level planar (ULP). Our contributions are three-fold. First, we describe which trees are ULP and provide linear-time level planar drawing algorithms for any labeling. Second, we characterize ULP trees in terms of forbidden subtrees so that any other tree must contain a subtree homeomorphic to one of these. Third, we provide a linear-time recognition algorithm for ULP trees. © 2009 Elsevier B.V. All rights reserved.
• Estrella-Balderrama, A., Fowler, J. J., & Kobourov, S. G. (2009). Colored simultaneous geometric embeddings and universal pointsets. Proceedings of the 21st Annual Canadian Conference on Computational Geometry, CCCG 2009, 17-20.
  More info

  Abstract: A set of n points in the plane is a universal pointset for a given class of graphs, if any n-vertex graph in that class can be embedded in the plane so that vertices are mapped to points, edges are drawn with straight lines, and there are no crossings. A set of graphs defined on the same n vertices, which are partitioned into k colors, has a colored simultaneous geometric embedding if there exists a set of k-colored points in the plane such that each vertex can be mapped to a point of the same color, resulting in a straight-line plane drawing of each graph. We consider classes of trees and show that there exist universal or near universal pointsets for 3-colored cater- pillars, 3-colored radius-2 stars, and 2-colored spiders.
• Estrella-Balderrama, A., Fowler, J. J., & Kobourov, S. G. (2009). Graph simultaneous embedding tool, graphSET. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5417 LNCS, 169-180.
  More info

  Abstract: Problems in simultaneous graph drawing involve the layout of several graphs on a shared vertex set. This paper describes a Graph Simultaneous Embedding Tool, GraphSET, designed to allow the investigation of a wide range of embedding problems. GraphSET can be used in the study of several variants of simultaneous embedding including simultaneous geometric embedding, simultaneous embedding with fixed edges and colored simultaneous embedding with the vertex set partitioned into color classes. The tool has two primary uses: (i) studying theoretical problems in simultaneous graph drawing through the production of examples and counterexamples and (ii) producing layouts of given classes of graphs using built-in implementations of known algorithms. GraphSET along with movies illustrating its utility are available at http://graphset.cs.arizona.edu. © 2009 Springer Berlin Heidelberg.
• Frati, F., Kaufmann, M., & Kobourov, S. (2009). Constrained simultaneous and near-simultaneous embeddings. Journal of Graph Algorithms and Applications, 13(3), 447-465.
  More info

  Abstract: A geometric simultaneous embedding of two graphs G 1=(V 1,E 1) and G 2=(V 2,E 2) with a bijective mapping of their vertex sets γ:V 1 → V 2 is a pair of planar straight-line drawings Γ 1 of G 1 and Γ 2 of G 2, such that each vertex v2=γ(v1), with v1 ∈ V 1 and v2 ∈ V 2, is mapped in Γ 2 to the same point where v1 is mapped in Γ 1. In this paper we examine several constrained versions and a relaxed version of the geometric simultaneous embedding problem. We show that assuming that the input graphs do not share common edges does not yield larger classes of graphs that can be simultaneously embedded. Further, if a prescribed combinatorial embedding for each input graph must be preserved, then we can answer some of the problems that are still open in the standard geometric simultaneous embedding setting. Finally, we present some results on the near-simultaneous embedding problem, in which vertices are not forced to be placed exactly at the same, but just at 'nearby' points in different drawings.
• Gansner, E., Yifan, H. u., Kobourov, S., & Volinsky, C. (2009). Putting recommendations on the map - Visualizing clusters and relations. RecSys'09 - Proceedings of the 3rd ACM Conference on Recommender Systems, 345-348.
  More info

  Abstract: For users, recommendations can sometimes seem odd or counterintuitive. Visualizing recommendations can remove some of this mystery, showing how a recommendation is grouped with other choices. A drawing can also lead a user's eye to other options. Traditional 2D-embeddings of points can be used to create a basic layout, but these methods, by themselves, do not illustrate clusters and neighborhoods very well. In this paper, we propose the use of geographic maps to enhance the definition of clusters and neighborhoods, and consider the effectiveness of this approach in visualizing similarities and recommendations arising from TV shows. Copyright 2009 ACM.
• Duncan, C. A., Kobourov, S. G., & Sander, G. (2008). Graph drawing contest report. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4875 LNCS, 395-400.
  More info

  Abstract: This report describes the Annual Graph Drawing Contest, held in conjunction with the 2007 Graph Drawing Symposium in Sydney, Australia. The purpose of the contest is to monitor and challenge the current state of graph-drawing technology. © 2008 Springer-Verlag Berlin Heidelberg.
• Estrella-Balderrama, A., Frati, F., & Kobourov, S. G. (2008). Upward straight-line embeddings of directed graphs into point sets. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5344 LNCS, 122-133.
  More info

  Abstract: In this paper we consider the problem of characterizing the directed graphs that admit an upward straight-line embedding into every point set in convex or in general position. In particular, we show that no biconnected directed graph admits an upward straight-line embedding into every point set in convex position, and we provide a characterization of the Hamiltonian directed graphs that admit upward straight-line embeddings into every point set in general or in convex position. We also describe how to construct upward straight-line embeddings of directed paths into convex point sets and we prove that for directed trees such embeddings do not always exist. Further, we investigate the related problem of upward simultaneous embedding without mapping, proving that deciding whether two directed graphs admit an upward simultaneous embedding without mapping is NP-hard. © 2008 Springer Berlin Heidelberg.
• Fowler, J. J., & Kobourov, S. G. (2008). Characterization of unlabeled level planar graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4875 LNCS, 37-49.
  More info

  Abstract: We present the set of planar graphs that always have a simultaneous geometric embedding with a strictly monotone path on the same set of n vertices, for any of the n! possible mappings. These graphs are equivalent to the set of unlabeled level planar (ULP) graphs that are level planar over all possible labelings. Our contributions are twofold. First, we provide linear time drawing algorithms for ULP graphs. Second, we provide a complete characterization of ULP graphs by showing that any other graph must contain a subgraph homeomorphic to one of seven forbidden graphs. © 2008 Springer-Verlag Berlin Heidelberg.
• Fowler, J. J., & Kobourov, S. G. (2008). Minimum level nonplanar patterns for trees. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4875 LNCS, 69-75.
  More info

  Abstract: Minimum Level Nonplanar (MLNP) patterns play the role for level planar graphs that the forbidden Kuratowksi subdivisions K 5 and K 3,3 play for planar graphs. We add two (MLNP) patterns for trees to the previous set of tree patterns given by Healy et al. [4]. Neither of these patterns match any of the previous patterns. We show that this new set of patterns completely characterizes level planar trees. © 2008 Springer-Verlag Berlin Heidelberg.
• Fowler, J. J., Jünger, M., Kobourov, S. G., & Schulz, M. (2008). Characterizing Simultaneous Embedding with Fixed Edges. Electronic Notes in Discrete Mathematics, 31(C), 41-44.
  More info

  Abstract: A set of planar graphs share a simultaneous embedding if they can be drawn on the same vertex set V of n vertices in the plane without crossings between edges of the same graph. Fixed edges are common edges between graphs that share the same Jordan curve in the simultaneous drawing. We give a necessary condition for when pairs of graphs can have a simultaneous embedding with fixed edges (SEFE). This allows us to determine for which (outer)planar graphs always have a SEFE with all (outer)planar graphs with O (n2 lg n) time drawing algorithms. This allows us to decide in O (n) time whether a pair of biconnected outerplanar graphs has a SEFE. © 2008.
• Fowler, J. J., Jünger, M., Kobourov, S., & Schulz, M. (2008). Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5344 LNCS, 146-158.
  More info

  Abstract: A set of planar graphs share a simultaneous embedding if they can be drawn on the same vertex set V in the Euclidean plane without crossings between edges of the same graph. Fixed edges are common edges between graphs that share the same simple curve in the simultaneous drawing. Determining in polynomial time which pairs of graphs share a simultaneous embedding with fixed edges (SEFE) has been open. We give a necessary and sufficient condition for whether a SEFE exists for pairs of graphs whose union is homeomorphic to K 5 or K 3,3. This allows us to characterize the class of planar graphs that always have a SEFE with any other planar graph. We also characterize the class of biconnected outerplanar graphs that always have a SEFE with any other outerplanar graph. In both cases, we provide efficient algorithms to compute a SEFE. Finally, we provide a linear-time decision algorithm for deciding whether a pair of biconnected outerplanar graphs has a SEFE. © 2008 Springer Berlin Heidelberg.
• Frati, F., Kaufmann, M., & Kobourov, S. G. (2008). Constrained simultaneous and near-simultaneous embeddings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4875 LNCS, 268-279.
  More info

  Abstract: A geometric simultaneous embedding of two graphs G 1∈= ∈(V 1,E 1) and G 2∈=∈(V 2,E 2) with a bijective mapping of their vertex sets γ: V 1 →V 2 is a pair of planar straight-line drawings Γ 1 of G 1 and Γ 2 of G 2, such that each vertex v 2∈=∈γ(v 1) is mapped in Γ 2 to the same point where v 1 is mapped in Γ 1, where v 1∈ ∈V 1 and v 2∈ ∈V 2. In this paper we examine several constrained versions and a relaxed version of the geometric simultaneous embedding problem. We show that if the input graphs are assumed to share no common edges this does not seem to yield large classes of graphs that can be simultaneously embedded. Further, if a prescribed combinatorial embedding for each input graph must be preserved, then we can answer some of the problems that are still open for geometric simultaneous embedding. Finally, we present some positive and negative results on the near-simultaneous embedding problem, in which vertices are not mapped exactly to the same but to "near" points in the different drawings. © 2008 Springer-Verlag Berlin Heidelberg.
• Gajer, P., Goodrich, M., & Kobourov, S. (2008). A multi-dimensional approach to force-directed layouts of large graphs. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 29(1), 3-18.
  More info

  We present a novel hierarchical force-directed method for drawing large graphs. Given a graph G = (V, E), the algorithm produces an embedding for G in an Euclidean space E of any dimension. A two or three dimensional drawing of the graph is then obtained by projecting a higher-dimensional embedding into a two or three dimensional subspace of E. Such projections typically result in drawings that are "smoother" and more symmetric than direct drawings in 2D and 3D.
• Kobourov, S. G., & Landis, M. (2008). Morphing planar graphs in spherical space. Journal of Graph Algorithms and Applications, 12(1), 113-127.
  More info

  Abstract: We consider the problem of intersection-free planar graph morphing, and in particular, a generalization from Euclidean space to spherical space. We show that there exists a continuous and intersection-free morph between two sphere drawings of a maximally planar graph, provided that both sphere drawings have convex inscribed polytopes, where sphere drawings are the spherical equivalent of plane drawings: intersection-free geodesic-arc drawings. In addition, we describe a morphing algorithm along with its implementation. Movies of sample morphs can be found at http://smorph.cs.arizona.edu.
• Brandenburg, F., Eppstein, D., Goodrich, M., Kobourov, S., Liotta, G., Mutzel, P., & Liotta, G. (2007). Selected open problems in graph drawing. GRAPH DRAWING, 2912, 515-539.
  More info

  In this manuscript, we present several challenging and interesting open problems in graph drawing. The goal of the listing in this paper is to stimulate future research in graph drawing.
• Brandes, U., Erten, C., Fowler, J., Frati, F., Geyer, M., Gutwenger, C., Hong, S., Kaufmann, M., Kobourov, S. G., Liotta, G., Mutzel, P., & Symvonis, A. (2007). Colored simultaneous geometric embeddings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4598 LNCS, 254-263.
  More info

  Abstract: We introduce the concept of concept simultaneous geometric embeddings as a generalization of simultaneous graph embeddings with and without mapping. We show that there exists a universal pointset of size n for paths colored with two or three colors. We use these results to show that colored simultaneous geometric embeddings exist for: (1) a 2-colored tree together with any number of 2-colored paths and (2) a 2-colored outerplanar graph together with any number of 2-colored paths. We also show that there does not exist a universal pointset of size n for paths colored with five colors. We finally show that the following simultaneous embeddings are not possible: (1) three 6-colored cycles, (2) four 6-colored paths, and (3) three 9-colored paths. © Springer-Verlag Berlin Heidelberg 2007.
• Cappos, J., Estrella-Balderrama, A., Fowler, J. J., & Kobourov, S. G. (2007). Simultaneous graph embedding with bends and circular arcs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4372 LNCS, 95-107.
  More info

  Abstract: We consider the problem of simultaneous embedding of planar graphs. We demonstrate how to simultaneously embed a path and an n-level planar graph and how to use radial embeddings for curvilinear simultaneous embeddings of a path and an outerplanar graph. We also show how to use star-shaped levels to find 2-bends per path edge simultaneous embeddings of a path and an outerplanar graph. All embedding algorithms run in O(n) time. © Springer-Verlag Berlin Heidelberg 2007.
• Duncan, C. A., Efrat, A., Kobourov, S., & Wenk, C. (2007). Drawing with fat edges. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 17(5), 1143-1163.
  More info

  Traditionally, graph drawing algorithms represent vertices as circles and edges as curves connecting the vertices. We introduce the problem of drawing with "fat" edges, i.e., with edges of variable thickness. The thickness of an edge is often used as a visualization cue, to indicate importance, or to convey some additional information. We present a model for drawing with fat edges and a corresponding efficient polynomial time algorithm that uses the model.
• Duncan, C. A., Klau, G., Kobourov, S. G., & Sander, G. (2007). Graph-drawing contest report. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4372 LNCS, 448-452.
  More info

  Abstract: This report describes the Thirteenth Annual Graph Drawing Contest, held in conjunction with the 2006 Graph Drawing Symposium in Karlsruhe, Germany. The purpose of the contest is to monitor and challenge the current state of the graph-drawing technology. © Springer-Verlag Berlin Heidelberg 2007.
• Estrella-Balderrama, A., Fowler, J. J., & Kobourov, S. G. (2007). Characterization of unlabeled level planar trees. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4372 LNCS, 367-379.
  More info

  Abstract: Consider a graph G drawn in the plane so that each vertex lies on a distinct horizontal line ℓj = {(x, j) |x ∈ ℝ}. The bijection φ that maps the set of n vertices V to a set of distinct horizontal lines ℓj forms a labeling of the vertices. Such a graph G with the labeling φ is called an n-level graph and is said to be n-level planar if it can be drawn with straight-line edges and no crossings while keeping each vertex on its own level. In this paper, we consider the class of trees that are n-level planar regardless of their labeling. We call such trees unlabeled level planar (ULP). Our contributions are three-fold. First, we provide a complete characterization of ULP trees in terms of a pair of forbidden subtrees. Second, we show how to draw ULP trees in linear time. Third, we provide a linear time recognition algorithm for ULP trees. © Springer-Verlag Berlin Heidelberg 2007.
• Kobourov, S. G., & Landis, M. (2007). Morphing planar graphs in spherical space. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4372 LNCS, 306-317.
  More info

  Abstract: We consider the problem of intersection-free planar graph morphing, and in particular, a generalization from Euclidean space to spherical space. We show that there exists a continuous and intersection-free morph between two sphere drawings of a maximally planar graph, provided that both sphere drawings have convex inscribed polytopes, where sphere drawings are the spherical equivalent of plane drawings: intersection-free geodesic-arc drawings. In addition, we describe a morphing algorithm along with its implementation. Movies of sample morphs can be found at http://www.cs.arizona.edu/~mlandis/smorph. © Springer-Verlag Berlin Heidelberg 2007.
• Cheng, C., Duncan, C., Goodrich, M., Kobourov, S., & Kratochvil, J. (2006). Drawing planar graphs with circular arcs. GRAPH DRAWING, 1731, 117-126.
  More info

  In this pager we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small thawing area. We present a lower bound on the area of drawings in which edges are drawn using exactly one circular are. We also give an algorithm for drawing n-vertex plannr graphs such that the edges are sequences of two continuos circular arcs. The algorithm runs in O(n) time and embeds the graph on the O(n) x O(n) grid, while maintaining theta (1/d (v)) angular resolution, where d(v) is the degree of vertex v. Since in this case we use circular arcs of infinite radius, this is also the first algorithm to simultaneously achieve good angular resolution, small area and at most one bend per edge using straight-line segments. Finally, we show how tu create drawings in which edges are smooth C(1)-continuous curves, represented by a sequence of at most three circular arcs.
• Duncan, C. A., Kobourov, S. G., & S., V. (2006). Optimal constrained graph exploration. ACM Transactions on Algorithms, 2(3), 380-402.
  More info

  Abstract: We address the problem of constrained exploration of an unknown graph G = ( V, E) from a given start node s with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. In both variations of the problem, the robot can only move along the edges of the graph, for example, it cannot jump between nonadjacent nodes. In the tethered robot case, if the tether (rope) has length l, then the robot must remain within distance l from the start node s. In the second variation, a fuel tank of limited capacity forces the robot to return to s after traversing C edges. The efficiency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. We present an algorithm for a tethered robot that explores the graph in Θ(|E|) edge traversals. The problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a Θ(|E|) algorithm. This improves on the previous best-known bound of O (|E|+ |V| log 2 |V|). Since the lower bound for the graph exploration problems is Ω(|E|), our algorithm is optimal within a constant factor. © 2006 ACM.
• Duncan, C. A., Kobourov, S. G., & Wagner, D. (2006). Graph-drawing contest report. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3843 LNCS, 528-531.
  More info

  Abstract: This report describes the Twelfth Annual Graph Drawing Contest, held in conjunction with the 2005 Graph Drawing Symposium in Limerick, Ireland. The purpose of the contest is to monitor and challenge the current state of graph-drawing technology. © Springer-Verlag Berlin Heidelberg 2005.
• Estrella-Balderrama, A., Fowler, J. J., & Kobourov, S. G. (2006). Characterization of unlabeled level planar trees. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 42(6-7), 704-721.
  More info

  Consider a graph G with vertex set V in which each of the n vertices is assigned a number from the set {1,..., k) for some positive integer k. This assignment phi is a labeling if all k numbers are used. If G does not assign adjacent vertices the same label, then G forms a leveling that partitions V into k levels. If G has a planar drawing in which the y-coordinate of all vertices match their labels and edges are drawn strictly y-monotone. then G is level planar. In this paper, we consider the class of level trees that are level planar regardless of their labeling. We call such trees unlabeled level planar (ULP). Our contributions are threefold. First, we describe which trees are ULP and provide linear-time level planar drawing algorithms for any labeling. Second, we characterize ULP trees in terms of forbidden subtrees so that any other tree must contain a subtree homeomorphic to one of these. Third, we provide a linear-time recognition algorithm for ULP trees. (C) 2009 Elsevier B.V. All rights reserved.
• Kenthapadi, K., Panigrahy, R., Achlioptas, D., Azar, Y., Brightwell, G., Cheriyan, J., Gustedt, J., Hell, P., Iacono, J., Kobourov, S., Kolliopoulos, S., Ladner, R., Lewenstein, M., Mahdian, M., Plaxton, G., Reed, B., Rubinfeld, R., Russell, A., Sethuraman, J., , Skutella, M., et al. (2006). Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms: Preface. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, xiii.
• Cheng, C., Duncan, C., Goodrich, M., & Kobourov, S. (2005). Drawing planar graphs with circular arcs. DISCRETE & COMPUTATIONAL GEOMETRY, 25(3), 405-418.
  More info

  In this paper we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present a lower bound on the area of drawings in which edges are drawn using exactly one circular are. We also give an algorithm for drawing n-vertex planar graphs such that the edges are sequences of two continuous circular area. The algorithm runs in O(n) time and embeds the graph on the O(n) x O(n) grid, while maintaining Theta (1/d(upsilon)) angular resolution, where d(upsilon) is the degree of vertex upsilon. Since in this case we use circular arcs of infinite radius, this is also the first algorithm that simultaneously achieves good angular resolution, small area, and at most one bend per edge using straight-line segments. Finally, we show how to create drawings in which edges are smooth C-1-continuous curves, represented by a sequence of at most three circular arcs.
• Erten, C., & Kobourov, S. G. (2005). Simultaneous embedding of a planar graph and its dual on the grid. Theory of Computing Systems, 38(3), 313-327.
  More info

  Abstract: Traditional representations of graphs and their duals suggest that the dual vertices should be placed inside their corresponding primal faces, and the edges of the dual graph should only cross their corresponding primal edges. We consider the problem of simultaneously embedding a planar graph and its dual on a small integer grid such that the edges are drawn as straight-line segments and the only crossings are between primal - dual pairs of edges. We provide an O(n) time algorithm that simultaneously embeds a 3-connected planar graph and its dual on a (2n - 2) × (2n - 2) integer grid, where n is the total number of vertices in the graph and its dual. All the edges are drawn as straight-line segments except for one edge on the outer face, which is drawn using two segments. © 2005 Springer Science+Business Media, Inc.
• Erten, C., & Kobourov, S. G. (2005). Simultaneous embedding of planar graphs with few bends. Journal of Graph Algorithms and Applications, 9(3), 347-364.
  More info

  Abstract: We consider several variations of the simultaneous embedding problem for planar graphs. We begin with a simple proof that not all pairs of planar graphs have simultaneous geometric embeddings. However, using bends, pairs of planar graphs can be simultaneously embedded on the O(n 2) × O(n 2) grid, with at most three bends per edge, where n is the number of vertices. The O(n) time algorithm guarantees that two corresponding vertices in the graphs are mapped to the same location in the final drawing and that both the drawings are without crossings. The special case when both input graphs are trees has several applications, such as contour tree simplification and evolutionary biology. We show that if both input graphs are trees, only one bend per edge is required. The O(n) time algorithm guarantees that both drawings are crossings-free, corresponding tree vertices are mapped to the same locations, and all vertices (and bends) are on the O(n 2) × O(n 2) grid (O(n 3) × O(n 3) grid). For the special case when one of the graphs is a tree and the other is a path we can find simultaneous embeddings with fixed-edges. That is, we can guarantee that corresponding vertices are mapped to the same locations and that corresponding edges are drawn the same way. We describe an O(n) time algorithm for simultaneous embeddings with fixededges for tree-path pairs with at most one bend per tree-edge and no bends along path edges, such that all vertices (and bends) are on the O(n) × O(n 2) grid, (O(n 2) × O(n 3) grid).
• Erten, C., Harding, P., Kobourov, S., Wampler, K., Yee, G., & Liotta, G. (2005). GraphAEL: Graph animations with evolving layouts. GRAPH DRAWING, 2912, 98-110.
  More info

  GraphAEL extracts three types of evolving graphs from the Graph Drawing literature and creates 2D and 3D animations of the evolutions. We study citation graphs, topic graphs, and collaboration graphs. We also create difference graphs which capture the nature of change between two given time periods. GraphAEL can be accessed online at http://graphael.cs.arizona.edu.
• Erten, C., Kobourov, S. G., Le, V., & Navabi, A. (2005). Simultaneous graph drawing: Layout algorithms and visualization schemes. Journal of Graph Algorithms and Applications, 9(1), 165-182.
  More info

  Abstract: In this paper we consider the problem of drawing and displaying a series of related graphs, i.e., graphs that share all, or parts of the same node set. We present three algorithms for simultaneous graph drawing and three visualization schemes. The algorithms are based on a modification of the force-directed algorithm that allows us to take into account node weights and edge weights in order to achieve mental map preservation while obtaining individually readable drawings. The algorithms and visualization schemes have been implemented and the system can be downloaded at http://simg.cs.arizona.edu/.
• Kobourov, S. G., & Wampler, K. (2005). Non-Euclidean spring embedders. IEEE Transactions on Visualization and Computer Graphics, 11(6), 757-767.
  More info

  PMID: 16270867;Abstract: We present a conceptually simple approach to generalizing force-directed methods for graph layout from Euclidean geometry to Riemannian geometries. Unlike previous work on non-Euclidean force-directed methods, ours is not limited to special classes of graphs, but can be applied to arbitrary graphs. The method relies on extending the Euclidean notions of distance, angle, and force-interactions to smooth non-Euclidean geometries via projections to and from appropriately chosen tangent spaces. In particular, we formally describe the calculations needed to extend such algorithms to hyperbolic and spherical geometries. We also study the theoretical and practical considerations that arise when working with non-Euclidean geometries. © 2005 IEEE.
• Kobourov, S. G., Pavlou, K., Cappos, J., Stepp, M., Miles, M., & Wixted, A. (2005). Collaboration with DiamondTouch. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3585 LNCS, 986-989.
  More info

  Abstract: We study the performance of collaborative spatial/visual tasks under different input configurations. The configurations used are a traditional mouse-monitor, a shared-monitor with multiple-mice, and a multi-user input device (DiamondTouch). Our experiments indicate that there is a significant variation in performance for the different configurations with pairs of users, while there is no such variation with individual users. The traditional configuration is not well-suited for collaborative tasks, and even after augmenting it to a shared monitor with multiple-mice it is still significantly inferior to the multi-user input device. © IFIP International Federation for Information Processing 2005.
• Abello, J., Kobourov, S. G., & Yusufov, R. (2004). Visualizing large graphs with compound-fisheye views and treemaps. Lecture Notes in Computer Science, 3383, 431-441.
  More info

  Abstract: Compound-fisheye views are introduced as a method for the display and interaction with large graphs. The method relies on a hier-archical clustering of the graph, and a generalization of the traditional fisheye view, together with a treemap representation of the cluster tree. © Springer-Verlag Berlin Heidelberg 2004.
• Biedl, T., Demaine, E. D., Duncan, C. A., Fleischer, R., & Kobourov, S. G. (2004). Tight bounds on maximal and maximum matchings. Discrete Mathematics, 285(1-3), 7-15.
  More info

  Abstract: In this paper, we study lower bounds on the size of maximal and maximum matchings in 3-connected planar graphs and graphs with bounded maximum degree. For each class, we give a lower bound on the size of matchings, and show that the bound is tight for some graph within the class. © 2004 Elsevier B.V. All rights reserved.
• Brandenburg, F. J., Duncan, C. A., Gansner, E. R., & Kobourov, S. G. (2004). Graph-drawing contest report. Lecture Notes in Computer Science, 3383, 512-516.
  More info

  Abstract: This report describes the Eleventh Annual Graph Drawing Contest, held in conjunction with the 2004 Graph Drawing Symposium in New York, USA. The purpose of the contest is to monitor and challenge the current state of the graph-drawing technology. © Springer-Verlag Berlin Heidelberg 2004.
• Brandenburg, F., Eppstein, D., Goodrich, M. T., Kobourov, S., Liotta, G., & Mutzel, P. (2004). Selected open problems in graph drawing. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2912, 515-539.
  More info

  Abstract: In this manuscript, we present several challenging and interesting open problems in graph drawing. The goal of the listing in this paper is to stimulate future research in graph drawing. © Springer-Verlag 2004.
• Brass, P., Cenek, E., Duncan, C. A., Efrat, A., Erten, C., Ismailescu, D. P., Kobourov, S. G., Lubiw, A., & Mitchell, J. S. (2004). On simultaneous planar graph embeddings. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 36(2), 117-130.
  More info

  We consider the problem of simultaneous embedding of planar graphs. There are two variants of this problem, one in which the mapping between the vertices of the two graphs is given and another in which the mapping is not given. We present positive and negative results for the two versions of the problem. Among the positive results with given mapping, we show that we can embed two paths on an n x n grid, and two caterpillar graphs on a 3n x 3n grid. Among the negative results with given mapping, we show that it is not always possible to simultaneously embed three paths or two general planar graphs. If the mapping is not given, we show that any number of outerplanar graphs can be embedded simultaneously on an O(n) x O(n) grid, and an outerplanar and general planar graph can be embedded simultaneously on an O(n(2)) x O(n(2)) grid. (c) 2006 Elsevier B.V. All rights reserved.
• Duncan, C. A., Eppstein, D., & Kobourov, S. G. (2004). The geometric thickness of low degree graphs. Proceedings of the Annual Symposium on Computational Geometry, 340-346.
  More info

  Abstract: We prove that the geometric thickness of graphs whose maximum degree is no more than four is two. All of our algorithms run in O(n) time, where n is the number of vertices in the graph. In our proofs, we present an embedding algorithm for graphs with maximum degree three that uses an n × n grid and a more complex algorithm for embedding a graph with maximum degree four. We also show a variation using orthogonal edges for maximum degree four graphs that also uses an n × n grid. The results have implications in graph theory, graph drawing, and VLSI design.
• Efrat, A., Kobourov, S. G., & Lubiw, A. (2004). Computing homotopic shortest paths efficiently. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 35(3), 162-172.
  More info

  We give deterministic and randomized algorithms to find shortest paths homotopic to a given collection R of disjoint paths that wind amongst n point obstacles in the plane. Our deterministic algorithm runs in time O(k(out) + k(in) log n + n root n), and the randomized algorithm runs in expected time O(k(out) + k(in) log n + n(log n)(1+epsilon)). Here k(in) is the number of edges in all the paths of Pi, and k(out) is the number of edges in the output paths. (c) 2006 Elsevier B.V. All rights reserved.
• Erten, C., & Kobourov, S. G. (2004). Simultaneous embedding of planar graphs with few bends. Lecture Notes in Computer Science, 3383, 195-205.
  More info

  Abstract: We present an O(n) time algorithm for simultaneous embedding of pairs of planar graphs on the O(n 2) × O(n 2) grid, with at most three bends per edge, where n is the number of vertices. For the case when the input graphs are both trees, only one bend per edge is required. We also describe an O(n) time algorithm for simultaneous embedding with fixed-edges for tree-path pairs on the O(n) × O(n 2) grid with at most one bend per tree-edge and no bends along path edges. © Springer-Verlag Berlin Heidelberg 2004.
• Erten, C., Harding, P. J., Kobourov, S. G., Wampler, K., & Yee, G. (2004). Exploring the computing literature using temporal graph visualization. Proceedings of SPIE - The International Society for Optical Engineering, 5295, 45-56.
  More info

  Abstract: We present a system for the visualization of computing literature with an emphasis on collaboration patterns, interactions between related research specialties and the evolution of these characteristics through time. Our computing literature visualization system, has four major components: A mapping of bibliographical data to relational schema coupled with an RDBMS to store the relational data, an interactive GUI that allows queries and the dynamic construction of graphs, a temporal graph layout algorithm, and an interactive visualization tool. We use a novel technique for visualization of large graphs that evolve through time. Given a dynamic graph, the layout algorithm produces two-dimensional representations of each timeslice, while preserving the mental map of the graph from one slice to the next. A combined view, with all the timeslices can also be viewed and explored. For our analysis we use data from the Association of Computing Machinery's Digital Library of Scientific Literature which contains more than one hundred thousand research papers and authors. Our system can be found online at http://tgrip.cs.arizona.edu.
• Erten, C., Harding, P. J., Kobourov, S. G., Wampler, K., & Yee, G. (2004). GraphAEL: Graph Animations with Evolving Layouts. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2912, 98-110.
  More info

  Abstract: GraphAEL extracts three types of evolving graphs from the Graph Drawing literature and creates 2D and 3D animations of the evolutions. We study citation graphs, topic graphs, and collaboration graphs. We also create difference graphs which capture the nature of change between two given time periods. GraphAEL can be accessed online at http://graphael.cs.arizona.edu. © Springer-Verlag 2004.
• Erten, C., Kobourov, S. G., & Pitta, C. (2004). Intersection-free morphing of planar graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2912, 320-331.
  More info

  Abstract: Given two different drawings of a planar graph we consider the problem of morphing one drawing into the other. We designed and implemented an algorithm for intersection-free morphing of planar graphs. Our algorithm uses a combination of different techniques to achieve smooth transformations: rigid morphing, compatible triangulations, as well as morphing based on interpolation of the convex representations of the graphs. Our algorithm can morph between drawings with straight-line segments, bends, and curves. Our system is implemented in Java and available as an applet at http://gmorph.cs.arizona.edu. © Springer-Verlag 2004.
• Erten, C., Kobourov, S. G., & Pitta, C. (2004). Morphing planar graphs. Proceedings of the Annual Symposium on Computational Geometry, 451-452.
  More info

  Abstract: An efficient algorithm and implementation for morphing planar graphs is discussed. The five steps in the algorithm are: introduction of bend vertices, introduction of convex bounding box, compatible triangulations, affine transformation morphs, and barycentric-representation morph. The algorithm is implemented in the JAVA programming language. The main objective is to find a morph that does not introduce crossings in the intermediate drawing througout the transformation.
• Erten, C., Kobourov, S. G., Vu, L. e., & Navabi, A. (2004). Simultaneous graph drawing: layout algorithms and visualization schemes. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2912, 437-449.
  More info

  Abstract: In this paper we consider the problem of drawing and displaying a series of related graphs, i.e., graphs that share all, or parts of the same vertex set. We designed and implemented three different algorithms for simultaneous graph drawing and three different visualization schemes. The algorithms are based on a modification of the force-directed algorithm that allows us to take into account vertex weights and edge weights in order to achieve mental map preservation while obtaining individually readable drawings. The implementation is in Java and the system can be downloaded at http://simg.cs.arizona.edu/. © Springer-Verlag 2004.
• Erten, C., Kobourov, S., & Pach, J. (2004). Simultaneous embedding of planar graphs with few bends. GRAPH DRAWING, 3383, 195-205.
  More info

  We present an O(n) time algorithm for simultaneous embedding of pairs of planar graphs on the O(n(2)) x O(n(2)) grid, with at most three bends per edge, where n is the number of vertices. For the case when the input graphs are both trees, only one bend per edge is required. We also describe an O(n) time algorithm for simultaneous embedding with fixed-edges for tree-path pairs on the O(n) x O(n(2)) grid with at most one bend per tree-edge and no bends along path edges.
• Forrester, D., Kobourov, S. G., Navabi, A., Wampler, K., & Yee, G. V. (2004). Graphael: A system for generalized force-directed layouts. Lecture Notes in Computer Science, 3383, 454-464.
  More info

  Abstract: The graphael system implements several traditional force-directed layout methods, as well as several novel layout methods for non-Euclidean geometries, including hyperbolic and spherical. The system can handle large graphs, using multi-scale variations of the forcedirected methods. Moreover, graphael can layout and visualize graphs that evolve though time, using static views, animation, and morphing. The implementation includes a powerful interface that allows the user to put together existing algorithms and visualization techniques, and to easily add new ones. The system is written in Java and is available as a downloadable program or as an applet at http://graphael.cs. arizona.edu. © Springer-Verlag Berlin Heidelberg 2004.
• Gajer, P., Goodrich, M. T., & Kobourov, S. G. (2004). A multi-dimensional approach to force-directed layouts of large graphs. Computational Geometry: Theory and Applications, 29(1), 3-18.
  More info

  Abstract: We present a novel hierarchical force-directed method for drawing large graphs. Given a graph G=(V,E), the algorithm produces an embedding for G in an Euclidean space E of any dimension. A two or three dimensional drawing of the graph is then obtained by projecting a higher-dimensional embedding into a two or three dimensional subspace of E. Such projections typically result in drawings that are "smoother" and more symmetric than direct drawings in 2D and 3D. In order to obtain fast placement of the vertices of the graph our algorithm employs a multi-scale technique based on a maximal independent set filtration of vertices of the graph. While most existing force-directed algorithms begin with an initial random placement of all the vertices, our algorithm attempts to place vertices "intelligently", close to their final positions. Other notable features of our approach include a fast energy function minimization strategy and efficient memory management. Our implementation of the algorithm can draw graphs with tens of thousands of vertices using a negligible amount of memory in less than one minute on a 550 MHz Pentium PC. © 2004 Elsevier B.V.
• Kobourov, S. G., & Pitta, C. (2004). An interactive multi-user system for simultaneous graph drawing. Lecture Notes in Computer Science, 3383, 492-501.
  More info

  Abstract: In this paper we consider the problem of simultaneous drawing of two graphs. The goal is to produce aesthetically pleasing drawings for the two graphs by means of a heuristic algorithm and with human assistance. Our implementation uses the DiamondTouch table, a multi-user, touch-sensitive input device, to take advantage of direct physical interaction of several users working collaboratively. The system can be downloaded at http://dt.cs.arizona. edu where it is also available as an applet. © Springer-Verlag Berlin Heidelberg 2004.
• Kobourov, S. G., & Wampler, K. (2004). Non-euclidean spring embedders. Proceedings - IEEE Symposium on Information Visualization, INFO VIS, 207-214.
  More info

  Abstract: We present a method by which force-directed algorithms for graph layouts can be generalized to calculate the layout of a graph in an arbitrary Riemannian geometry. The method relies on extending the Euclidean notions of distance, angle, and force-interactions to smooth non-Euclidean geometries via projections to and from appropriately chosen tangent spaces. In particular, we formally describe the calculations needed to extend such algorithms to hyperbolic and spherical geometries. © 2004 IEEE.
• Kobourov, S., Pitta, C., & Pach, J. (2004). An interactive multi-user system for simultaneous graph drawing. GRAPH DRAWING, 3383, 492-501.
  More info

  In this paper we consider the problem of simultaneous drawing of two graphs. The goal is to produce aesthetically pleasing drawings for the two graphs by means of a heuristic algorithm and with human assistance. Our implementation uses the DiamondTouch table, a multiuser, touch-sensitive input device, to take advantage of direct physical interaction of several users working collaboratively. The system can be downloaded at http://dt.cs.arizona.edu where it is also available as an applet.
• Duncan, C. A., & Kobourov, S. G. (2003). Polar coordinate drawing of planar graphs with good angular resolution. Journal of Graph Algorithms and Applications, 7(4), 311-333.
  More info

  Abstract: We present a novel way to draw planar graphs with good angular resolution. We introduce the polar coordinate representation and describe a family of algorithms for constructing it. The main advantage of the polar representation is that it allows independent control over grid size and bend positions. We first describe a standard (Cartesian) representation algorithm, CRA, which we then modify to obtain a polar representation algorithm, PRA. In both algorithms we are concerned with the following drawing criteria: angular resolution, bends per edge, vertex resolution, bend-point resolution, edge separation, and drawing area. The CRA algorithm achieves 1 bend per edge, unit vertex and bend resolution, √2/2 edge separation, 5n x 5n/2 drawing area and 1/2d(v) angular resolution, where d(v) is the degree of vertex v. The PRA algorithm has an improved angular resolution of π/4d(v), 1 bend per edge, and unit vertex resolution. For the PRA algorithm, the bend-point resolution and edge separation are parameters that can be modi.ed to achieve di.erent types of drawings and drawing areas. In particular, for the same parameters as the CRA algorithm (unit bend-point resolution and √2/2 edge separation), the PRA algorithm creates a drawing of size 9n x 9n/2.
• Duncan, C. A., Goodrich, M. T., & Kobourov, S. G. (2003). Planarity-preserving clustering and embedding for large planar graphs. Computational Geometry: Theory and Applications, 24(2), 95-114.
  More info

  Abstract: In this paper we present a novel approach for cluster-based drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a clustering which satisfies the conditions for compound-planarity (c-planarity). Using the clustering, we obtain a representation of the graph as a collection of O(logn) layers, where each succeeding layer represents the graph in an increasing level of detail. At the same time, the difference between two graphs on neighboring layers of the hierarchy is small, thus preserving the viewer's mental map. The overall running time of the algorithm is O(nlogn), where n is the number of vertices of graph G. © 2002 Elsevier Science B.V. All rights reserved.
• Duncan, C. A., & Kobourov, S. G. (2002). Polar coordinate drawing of planar graphs with good angular resolution. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2265 LNCS, 407-421.
  More info

  Abstract: We present a novel way to draw planar graphs with good angular resolution. We introduce the polar coordinate representation and describe a family of algorithms which use polar representation. The main advantage of using a polar representation is that it allows us to exert independent control over grid size and bend positions. Polar coordinates allow us to specify different vertex resolution, bend-point resolution and edge separation. We first describe a standard (Cartesian) representation algorithm (CRA) which we then modify to obtain a polar representation algorithm (PRA). In both algorithms we are concerned with the following drawing criteria: angular resolution, bends per edge, vertex resolution, bend-point resolution, edge separation, and drawing area. The CRA algorithm achieves 1 bend per edge, unit vertex and bend resolution, √2/2 edge separation, 5n × 5n/2 drawing area and 1/2d(v) angular resolution, where d(v) is the degree of vertex v. The PRA algorithm has an improved angular resolution of φ/4d(v) 1 bend per edge, and unit vertex resolution. For the PRA algorithm, the bend-point resolution and edge separation are parameters that can be modified to achieve different types of drawings and drawing areas. In particular, for the same parameters as the CRA algorithm (unit bend-point resolution and √2/2 edge separation), the PRA algorithm creates a drawing of size 9n × 9n/2. © Springer-Verlag Berlin Heidelberg 2002.
• Erten, C., & Kobourov, S. G. (2002). Simultaneous embedding of a planar graph and its dual on the grid. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2518 LNCS, 575-587.
  More info

  Abstract: Traditional representations of graphs and their duals suggest the requirement that the dual vertices should be placed inside their corresponding primal faces, and the edges of the dual graph should cross only their corresponding primal edges. We consider the problem of simultaneously embedding a planar graph and its dual on a small integer grid such that the edges are drawn as straight-line segments and the only crossings are between primal-dual pairs of edges. We provide an O(n) time algorithm that simultaneously embeds a 3-connected planar graph and its dual on a (2n - 2) × (2n - 2) integer grid, where n is the total number of vertices in the graph and its dual. © Springer-Verlag Berlin Heidelberg 2002.
• Gajer, P., & Kobourov, S. G. (2002). GRIP: Graph Drawing with Intelligent Placement. Journal of Graph Algorithms and Applications, 6(3), 203-224.
  More info

  Abstract: This paper describes a system for Graph dRawing with Intelligent Placement, GRIP. The system is designed for drawing large graphs and uses a novel multi-dimensional force-directed method together with fast energy function minimization. The algorithm underlying the system employs a simple recursive coarsening scheme. Rather than being placed at random, vertices are placed intelligently, several at a time, at locations close to their final positions. The running time and space complexity of the system are near linear. The implementation is in C using OpenGL for 3D viewing. The GRIP system allows for drawing graphs with tens of thousands of vertices in under one minute on a mid-range PC. To the best of the authors' knowledge, GRIP surpasses the fastest previous algorithms. However, speed is not achieved at the expense of quality as the resulting drawings are quite aesthetically pleasing.
• Goodrich, M. T., & Kobourov, S. G. (2002). Preface. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2528 LNCS, V.
• Biedl, T., Demaine, E. D., Duncan, C. A., Fleischer, R., & Kobourov, S. G. (2001). Tight bounds on maximal and maximum matchings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2223 LNCS, 308-319.
  More info

  Abstract: In this paper, we study bounds on maximal and maximum matchings in special graph classes, speci.cally triangulated graphs and graphs with bounded maximum degree. For each class, we give a lower bound on the size of matchings, and prove that it is tight for some graph within the class. © 2001 Springer Berlin Heidelberg.
• Cheng, C. C., Duncan, C. A., Goodrich, M. T., & Kobourov, S. G. (2001). Drawing planar graphs with circular arcs. Discrete and Computanional Geometry, 25(3), 405-418.
  More info

  Abstract: In this paper we address the problem of drawing planar graphs with circular arcs while maintaining good angular resolution and small drawing area. We present a lower bound on the area of drawings in which edges are drawn using exactly one circular arc. We also give an algorithm for drawing n-vertex planar graphs such that the edges are sequences of two continuous circular arcs. The algorithm runs in O(n) time and embeds the graph on the O(n) × O(n) grid, while maintaining Θ(1/d(v)) angular resolution, where d(v) is the degree of vertex v. Since in this case we use circular arcs of infinite radius, this is also the first algorithm that simultaneously achieves good angular resolution, small area, and at most one bend per edge using straight-line segments. Finally, we show how to create drawings in which edges are smooth C1-continuous curves, represented by a sequence of at most three circular arcs.
• Duncan, C. A., Goodrich, M. T., & Kobourov, S. (2001). Balanced Aspect Ratio Trees: Combining the Advantages of k-d Trees and Octrees. Journal of Algorithms, 38(1), 303-333.
  More info

  Abstract: Given a set S of n points on ℝd, we show, for fixed d, how to construct in O(n log n) time a data structure we call the balanced aspect ratio (BAR) tree. A BAR tree is a binary space partition tree on S that has O(log n) depth in which every region is convex and "fat" (that is, has a bounded aspect ratio). While previous hierarchical data structures such as k-d trees, quadtrees, octrees, fair-split trees, and balanced box decompositions can guarantee some of these properties, we know of no previous data structure that combines all of these properties simultaneously. The BAR tree data structure has numerous applications ranging from geometric searching problems in fixed dimensional space to the visualization of graphs and three-dimensional worlds. © 2001 Academic Press.
• Duncan, C. A., Kobourov, S. G., & Kumar, V. A. (2001). Optimal constrained graph exploration. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 807-814.
  More info

  Abstract: We address the problem of exploring an unknown graph G = (V, E) from a given start node s with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. In both variations of the problem, the robot can only move along the edges of the graph, i.e, it cannot jump between non-adjacent vertices. In the tethered robot case, if the tether (rope) has length /, then the robot must remain within distance / from the start node s. In the second variation, a fuel tank of limited capacity forces the robot to return to s after traversing C edges. The efficiency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. We present an algorithm for a tethered robot which explores the graph in &Ogr;(|E|) edge traversais. The problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a &Ogr;(|E|) algorithm. This improves on the previous best known bound of &Ogr;(|E| + \V|2log 2|V|) in [4]. Since the lower bound for the graph exploration problems is |E|, our algorithm is optimal, thus answering the open problem of Awerbuch, Betke, Rivest, and Singh [3]. Copyright © 2009 ACM, Inc.
• Bridgeman, S., Goodrich, M. T., Kobourov, S. G., & Tamassia, R. (2000). PILOT: An interactive tool for learning and grading. SIGCSE Bulletin (Association for Computing Machinery, Special Interest Group on Computer Science Education), 139-143.
  More info

  Abstract: We describe a Web-based interactive system, called PILOT, for testing computer science concepts. The strengths of PILOT are its universal access and platform independence, its use as an algorithm visualization tool, its ability to test algorithmic concepts, its support for graph generation and layout, its automated grading mechanism, and its ability to award partial credit to proposed solutions.
• Bridgeman, S., Goodrich, M. T., Kobourov, S. G., & Tamassia, R. (2000). SAIL: A system for generating, archiving, and retrieving specialized assignments using LAT _EX. SIGCSE Bulletin (Association for Computing Machinery, Special Interest Group on Computer Science Education), 300-304.
  More info

  Abstract: In this paper we present a package for the creation of Specialized Assignments In LAT EX, SAIL. We describe several features which allow an instructor to create sufficiently different instances of the `same' problem so as to encourage student cooperation without fear of plagiarism. The SAIL package also provides support for grading aids and grading automation. In addition, we describe an on-line system for archiving homework problems in a database that can be easily searched and to which new parametrized problems can be easily added. Together, the SAIL package and the searchable database of problems offer a powerful tool for generating, archiving, and retrieving homework assignments (as well as tests and quizzes).
• Duncan, C. A., Goodrich, M. T., & Kobourov, S. G. (2000). Balanced aspect ratio trees and their use for drawing large graphs. Journal of Graph Algorithms and Applications, 4(3), 19-46.
  More info

  Abstract: We describe a new approach for cluster-based drawing of large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSP-type decomposition, called the balanced aspect ratio (BAR) tree, which guarantees that the cells produced are convex and have bounded aspect ratios. In addition, the tree depth is O(log n), and its construction takes O(n log n) time, where n is the number of points. We show that the BAR tree can be used to recursively divide a graph embedded in the plane into subgraphs of roughly equal size, such that the drawing of each subgraph has a balanced aspect ratio. As a result, we obtain a representation of a graph as a collection of O(log n) layers, where each succeeding layer represents the graph in an increasing level of detail. The overall running time of the algorithm is O(n log n+m+D 0(G)), where n and m are the number of vertices and edges of the graph G, and D 0(G) is the time it takes to obtain an initial embedding of G in the plane. In particular, if the graph is planar each layer is a graph drawn with straight lines and without crossings on the n × n grid and the running time reduces to O(n log n).
• Collberg, C., & Kobourov, S. (1999). Self plagiarism in computer science. COMMUNICATIONS OF THE ACM, 48(4), 88-94.
• Duncan, C. A., Goodrich, M. T., & Kobourov, S. (1999). Balanced aspect ratio trees: Combining the advantages of k-d trees and octrees. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 300-309.
  More info

  Abstract: Given a set S of n points in Rd, we show, for fixed d, how to construct in O(n log n) time a data structure we call the Balanced Aspect Ratio (BAR) tree. A BAR tree is a binary space partition tree on S that has O(log n) depth and in which every region is convex and `fat' (that is, has a bounded aspect ratio). While previous hierarchical data structures, such as k-d trees, quadtrees, octrees, fair-split trees, and balanced box decompositions can guarantee some of these properties, we know of no previous data structure that combines all of these properties simultaneously. The BAR tree data structure has numerous applications ranging from solving several geometric searching problems in fixed dimensional space to aiding in the visualization of graphs and three-dimensional worlds.
• Kobourov, S., & Wampler, K. (1999). Non-Euclidean spring embedders. IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, 11(6), 757-767.
  More info

  We present a conceptually simple approach to generalizing force-directed methods for graph layout from Euclidean geometry to Riemannian geometries. Unlike previous work on non-Euclidean force-directed methods, ours is not limited to special classes of graphs, but can be applied to arbitrary graphs. The method relies on extending the Euclidean notions of distance, angle, and force-interactions to smooth non-Euclidean geometries via projections to and from appropriately chosen tangent spaces. In particular, we formally describe the calculations needed to extend such algorithms to hyperbolic and spherical geometries. We also study the theoretical and practical considerations that arise when working with non-Euclidean geometries.
• Awerbuch, B., & Kobourov, S. G. (1998). Polylogarithmic-overhead piecemeal graph exploration. Proceedings of the Annual ACM Conference on Computational Learning Theory, 280-286.
  More info

  Abstract: We introduce a new traversal technique in the context of piecemeal exploration of unknown graphs. The problem of learning a graph via piecemeal exploration requires a robot to create a complete map of its environment, subject to two constraints. First, it cannot jump between non-adjacent vertices in one time step and second, it must return to a fixed starting point every so often. This paper presents the recursive piecemeal search (RPS) strategy together with an algorithm for the above problem. We are able to achieve O(log2 n) overhead (where n is the number of vertices), improving on previous results of Awerbuch, Betke, Rivest, and Singh which require O(nε) overhead. The graph is discovered via the recursive piecemeal search, which can be viewed as a combination of breadth-first and depth-first passes. The construction of RPS trees relies on the concept of sparse neighborhood covers and captures nicely the nature of the graph exploration problem.

Proceedings Publications

• Ahmed, A. R., Bodwin, G., Hamm, K., Kobourov, S. G., & Spence, R. (2021, Fall). On Additive Spanners in Weighted Graphs with Local Error. In 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG).
  More info

  This is an A-level conference in CORE.
• Ahmed, A. R., Hamm, K., Kobourov, S. G., Sahneh, F. D., & Spence, R. (2021, Spring). Multi-Level Weighted Additive Spanners. In Symposium of Experimental Algorithms, 16:1-16:23.
• Frank, F., Kaufmann, M., Kobourov, S. G., Mchedlidze, T., Pupyrev, S., Ueckerdt, T., & Wolff, A. (2021, Spring). Using the Metro-Map Metaphor for Drawing Hypergraphs. In 47th Intl. Conference on Current Trends in Theory and Practice of Computer Science, 361-372.
• Lim, H., & Kobourov, S. G. (2021, Fall). Visualizing The Intermediate Representation of Just-in-Time Compilers. In 29th International Symposium on Graph Drawing and Network Visualization (GD).
  More info

  This is an A-level conference in CORE.
• Ahmed, A. R., Bodwin, G., Sahneh, F. D., Kobourov, S. G., & Spence, R. (2020, Fall). Weighted Additive Spanners. In 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 401-413.
  More info

  This is an A-level conference in CORE.
• Ahmed, A. R., Sahneh, F. D., Hamm, K., Kobourov, S. G., & Spence, R. (2020, Fall). Kruskal-based approximation algorithm for the multi-level Steiner tree problem. In 28th Annual European Symposium on Algorithms (ESA).
  More info

  This is an A-level conference in CORE.
• Ahmed, R., de Luca, F., Devkota, S., Kobourov, S. G., & Li, M. (2020, Fall). Graph drawing via gradient descent,. In 28th International Symposium on Graph Drawing and Network Visualization (GD).
  More info

  This is an A-level conference in CORE.
• Arkin, E. M., Sahneh, F. D., Efrat, A., Frank, F., Fulek, R., Kobourov, S. G., & Mitchell, J. (2020, Summer). Computing (beta)-Stretch Paths in Drawings of Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 162.
• Cornelsen, S., Pfister, M., Foerster, H., Groneman, M., Hoffman, M., Kobourov, S. G., & Schneck, T. (2020, Fall). Drawing Shortest Paths in Geodetic Graphs. In 28th International Symposium on Graph Drawing and Network Visualization (GD).
  More info

  This is an A-level conference in CORE.
• Efrat, A., Fulek, R., Kobourov, S. G., & Toth, C. (2020, Fall). Polygons with Prescribed Angles in 2D and 3D. In 28th International Symposium on Graph Drawing and Network Visualization (GD).
  More info

  This is an A-level conference in CORE.
• Nusrat, S., Alam, J., & Kobourov, S. G. (2020, Summer). Recognition and Recall of Geographic Data In Cartograms. In 13th International Conference on Advanced Visual Interfaces (AVI).
• Perry, S., Yin, M., Gray, K., & Kobourov, S. G. (2020, Summer). Drawing Graphs on the Sphere. In 13th International Conference on Advanced Visual Interfaces (AVI).
• Purchase, H., Archambault, D., Kobourov, S. G., Noellenburg, M., Pupyrev, S., & Wu, H. (2020, Fall). The Turing Test for Graph Drawing Algorithms. In 28th International Symposium on Graph Drawing and Network Visualization (GD).
  More info

  This is an A-level conference in CORE.
• Wallinger, M., Jacobsen, B., Kobourov, S. G., & Noellenburg, M. (2020, Fall). On the Readability of Abstract Set Visualizations. In IEEE Transactions on Visualization and Computer Graphics.
  More info

  This paper was also accepted for publication at the IEEE Transactions on Visualization and Computer Graphics, as an invited submission from the best papers from PACIFICVIS.
• Ahmed, A. R., Hamm, K., Jebelli, M., Kobourov, S. G., Sahneh, F. D., & Spence, R. (2019). Approximation Algorithms and an Integer Program for Multi-level Graph Spanners. In Analysis of Experimental Algorithms - Special Event, SEA\({^2\)} 2019, Kalamata, Greece, June 24-29, 2019, Revised Selected Papers.
• Angelini, P., F\"{o}rster, H., Hoffmann, M., Kaufmann, M., Kobourov, S. G., Liotta, G., & Patrignani, M. (2019, Fall). The QuaSEFE Problem. In Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Prague, Czech Republic, September 17-20, 2019, Proceedings.
  More info

  This conference is ranked A in CORE
• De, L. F., Di, G. E., Hong, S., Kobourov, S., Lenhart, W., Liotta, G., Meijer, H., Tappini, A., & Wismath, S. (2019). Packing Trees into 1-planar Graphs. In 14th International Conference and Workshop on Algorithms and Computation (WALCOM).
• Devkota, S., Ahmed, A. R., Luca, F. D., Isaacs, K. E., & Kobourov, S. G. (2019, Fall). Stress-Plus-X (SPX) Graph Layout. In Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Prague, Czech Republic, September 17-20, 2019, Proceedings.
  More info

  This conference is ranked A in CORE
• Luca, F. D., Hossain, M. I., & Kobourov, S. G. (2019, Fall). Symmetry Detection and Classification in Drawings of Graphs. In Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Prague, Czech Republic, September 17-20, 2019, Proceedings.
  More info

  This conference is ranked A in CORE.This paper won the best paper award.
• Mamano, N., Efrat, A., Eppstein, D., Frishberg, D., Goodrich, M. T., Kobourov, S. G., Matias, P., & Polishchuk, V. (2019, Spring). New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs. In 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China.
  More info

  This conference is ranked A in CORE
• Nickel, S., Sondag, M., Meulemans, W., Chimani, M., Kobourov, S. G., Peltonen, J., & N\"{o}llenburg, M. (2019, Fall). Computing Stable Demers Cartograms. In Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, Prague, Czech Republic, September 17-20, 2019, Proceedings.
  More info

  This conference is ranked A in CORE
• Van, H., Musa, A., Chen, H., Kobourov, S. G., & Surdeanu, M. (2019). What does the language of foods say about us?. In Proceedings of the Tenth International Workshop on Health Text Mining and Information Analysis LOUHI, EMNLP 2019, Hong Kong, November 3, 2019.
• Ahmed, A. R., Angelini, P., Sahneh, F. D., Efrat, A., Glickenstein, D., Gronemann, M., Heinsohn, N., Kobourov, S. G., Spence, R., Watkins, J., & Wolff, A. (2018). Multi-Level Steiner Trees. In 17th International Symposium on Experimental Algorithms, SEA 2018, June 27-29, 2018, L'Aquila, Italy.
• Ahmed, A. R., Rahman, M. S., & Kobourov, S. G. (2018). Online Facility Assignment. In WALCOM: Algorithms and Computation - 12th International Conference, WALCOM 2018, Dhaka, Bangladesh, March 3-5, 2018, Proceedings.
• Angelini, P., Eades, P., Hong, S., Klein, K., Kobourov, S. G., Liotta, G., Navarra, A., & Tappini, A. (2018, fall). Turning Cliques into Paths to Achieve Planarity. In Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Barcelona, Spain, September 26-28, 2018, Proceedings.
  More info

  This conference is ranked A in CORE.
• Bell, D., Laparra, E., Kousik, A., Ishihara, T., Surdeanu, M., & Kobourov, S. (2018). Detecting Diabetes Risk from Social Media Activity. In Proceedings of the Ninth International Workshop on Health Text Mining and Information Analysis.
• Burd, R., Espy, K. A., Hossain, M. I., Kobourov, S. G., Merchant, N., & Purchase, H. C. (2018). GRAM: global research activity map. In Proceedings of the 2018 International Conference on Advanced Visual Interfaces, AVI 2018, Castiglione della Pescaia, Italy, May 29 - June 01, 2018.
• Chen, H., Soni, U., Lu, Y., Maciejewski, R., & Kobourov, S. G. (2018, fall). Same Stats, Different Graphs - (Graph Statistics and Why We Need Graph Drawings). In Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Barcelona, Spain, September 26-28, 2018, Proceedings.
  More info

  This conference is ranked A in CORE.
• Hossain, M. I., Kobourov, S. G., Purchase, H. C., & Surdeanu, M. (2018). REMatch: Research Expert Matching System. In 2018 International Symposium on Big Data Visual and Immersive Analytics, BDVA 2018, Konstanz, Germany, October 17-19, 2018.
• Luca, F. D., Hossain, M. I., Kobourov, S. G., Lubiw, A., & Mondal, D. (2018, fall). Recognition and Drawing of Stick Graphs. In Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Barcelona, Spain, September 26-28, 2018, Proceedings.
  More info

  This conference is ranked A in CORE.
• Luca, F. D., Kobourov, S. G., & Purchase, H. C. (2018, fall). Perception of Symmetries in Drawings of Graphs. In Graph Drawing and Network Visualization - 26th International Symposium, GD 2018, Barcelona, Spain, September 26-28, 2018, Proceedings.
  More info

  This conference is ranked A in CORE.
• Soni, U., Lu, Y., Hansen, B., Purchase, H. C., Kobourov, S., & Maciejewski, R. (2018). The perception of graph properties in graph layouts. In 20th IEEE Eurographics Conference on Visualization (EUROVIS, 37.
• Chimani, M., Felsner, S., Kobourov, S. G., Ueckerdt, T., Valtr, P., & Wolff, A. (2017, June). On the Maximum Crossing Number. In 28th International Workshop on Combinatorial Algorithms (IWOCA).
• Kindermann, P., Kobourov, S. G., Loffler, M., Nollenburg, M., Schulz, A., & Vogtenhuber, B. (2017, September). Lombardi Drawings of Knots and Links. In Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Boston, MA, USA, September 25-27, 2017, Revised Selected Papers.
  More info

  This conference is ranked A in CORE
• Kobourov, S. G., Angelini, P., Chaplick, S., De Luca, F., Fiala, J., Hancl, J., Heinsohn, N., Kaufmann, M., Kratochvil, J., & Valtr, P. (2017, September). On Vertex- and Empty-Ply Proximity Drawings. In Symposium on Graph Drawing and Network Visualization, 24-37.
  More info

  This conference is ranked A in CORE
• Kruiger, J. F., Rauber, P. E., Martins, R. M., Kerren, A., Kobourov, S. G., & Telea, A. (2017, June). Graph Layouts by t-SNE. In 19th IEEE Eurographics Conference on Visualization (EuroVis).
• Okoe, M., Jianu, R., & Kobourov, S. G. (2017, September). Revisited Experimental Comparison of Node-Link and Matrix Representations. In Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Boston, MA, USA, September 25-27, 2017, Revised Selected Papers.
  More info

  This paper won the "BEST PAPER AWARD".This conference is ranked A in CORE.
• Simonetto, P., Archambault, D. W., & Kobourov, S. G. (2017, September). Drawing Dynamic Graphs Without Timeslices. In Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Boston, MA, USA, September 25-27, 2017, Revised Selected Papers.
  More info

  This conference is ranked A in CORE.
• Welch, E., & Kobourov, S. G. (2017, June). Measuring Symmetry in Drawings of Graphs. In 19th IEEE Eurographics Conference on Visualization (EuroVis).
• Alam, M. J., Kobourov, S., Pupyrev, S., & Toeniskoetter, J. (2016, June). Weak Unit Disk and Interval Representation of Graphs. In International Workshop on Graph-Theoretic Concepts in Computer Science (WG), 237-251.
  More info

  This conference is ranked A in CORE.
• Angelini, P., Bekos, M. A., Bruckdorfer, T., Hancl, J., Kaufmann, M., Kobourov, S., Symvonis, A., & Valtr, P. (2016, September). Low ply drawings of trees. In International Symposium on Graph Drawing and Network Visualization (GD), 236-248.
  More info

  This conference is ranked A in CORE
• Bell, D., Freed, D., Huangfu, L., Surdeanu, M., & Kobourov, S. G. (2016, May). Towards Using Social Media to Identify Individuals at Risk for Preventable Chronic Illness. In 10th International Conference on Language Resources and Evaluation (LREC).
• De Luca, F., Di Giacomo, E., Didimo, W., Kobourov, S. G., & Liotta, G. (2016, December). An Experimental Study on the Ply Number of Straight-line Drawings. In 11th International Conference and Workshops on Algorithms and Computation (WALCOM), 135-148.
• Eppstein, D., Kindermann, P., Kobourov, S. G., Liotta, G., Lubiw, A., Maignan, A., Mondal, D., Vosoughpour, H., Whitesides, S., & Wismath, S. K. (2016). On the Planar Split Thickness of Graphs. In LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings.
• Nusrat, S., & Kobourov, S. G. (2016, June). The State of the Art in Cartograms. In 18th IEEE Eurographics Conference on Visualization (EuroVis).
• Saket, B., Scheidegger, C., & Kobourov, S. (2016, June). Comparing Node-Link and Node-Link-Group Visualizations From An Enjoyment Perspective. In 18th IEEE Eurographics Conference on Visualization (EuroVis).
• Alam, M. J., Eppstein, D., Kaufmann, M., Kobourov, S. G., Pupyrev, S., Schulz, A., & Ueckerdt, T. (2015). Contact Graphs of Circular Arcs. In Algorithms and Data Structures - 14th International Symposium, {WADS} 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings.
• Alam, M. J., Evans, W. S., Kobourov, S. G., Pupyrev, S., Toeniskoetter, J., & Ueckerdt, T. (2015). Contact Representations of Graphs in 3D. In Algorithms and Data Structures - 14th International Symposium, {WADS} 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings.
• Bekos, M. A., Kaufmann, M., Kobourov, S., & Veeramoni, S. (2015, January). The Maximum k-Differential Coloring Problem. In SOFSEM 2015: Theory and Practice of Computer Science.
• Bruckdorfer, T., Kaufmann, M., Kobourov, S. G., & Pupyrev, S. (2015). On Embeddability of Buses in Point Sets. In Graph Drawing and Network Visualization - 23rd International Symposium, {GD} 2015, Los Angeles, CA, USA, September 24-26, 2015, Revised Selected Papers.
• Kobourov, S. G., & Nusrat, S. (2015, May). Task Taxonomy for Cartograms. In 17th IEEE Eurographics Conference on Visualization (EuroVis short papers).
• Kobourov, S. G., Alam, J., & Veeramoni, S. (2015, May). Quantitative Measures for Cartogram Generation Techniques. In 17th IEEE Eurographics Conference on Visualization (EuroVis).
• Kobourov, S. G., Johnson, T., Acedo, C., & Nusrat, S. (2015, May). Analyzing the Evolution of the Internet. In 17th IEEE Eurographics Conference on Visualization (EuroVis short papers).
• Kobourov, S. G., Mchedlidze, T., & Vonessen, L. (2015, September). Gestalt Principles in Graph Drawing. In Graph Drawing and Network Visualization, 558--560.
• Kobourov, S. G., Scheidegger, C. E., & Saket, B. (2015, May). Towards Understanding Enjoyment and Flow in Information Visualization. In 17th IEEE Eurographics Conference on Visualization (EuroVis short papers)..
• Kobourov, S. G., Scheidegger, C. E., Saket, B., & Borner, K. (2015, May). Map-based Visualizations Increase Long-Term Recall of Data. In 17th IEEE Eurographics Conference on Visualization (EuroVis).
• Kobourov, S. G., di Giacomo, E., Didimo, W., Hong, S., Kaufmann, M., Liotta, G., Misue, K., Symvonis, A., & Yen, H. (2015, June). Low Ply Graph Drawing. In 6th IEEE International Conference on Information, Intelligence, Systems and Applications (IISA).
• Alam, M. J., Bekos, M. A., Kaufmann, M., Kindermann, P., Kobourov, S. G., & Wolff, A. (2014). Smooth Orthogonal Drawings of Planar Graphs. In LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings, 144--155.
• Alam, M. J., Eppstein, D., Goodrich, M. T., Kobourov, S. G., & Pupyrev, S. (2014). Balanced Circle Packings for Planar Graphs. In Graph Drawing - 22nd International Symposium, GD 2014, W"urzburg, Germany, September 24-26, 2014, Revised Selected Papers, 125--136.
• Alam, M. J., Kaufmann, M., Kobourov, S. G., & Mchedlidze, T. (2014). Fitting Planar Graphs on Planar Maps. In SOFSEM 2014: Theory and Practice of Computer Science - 40th International Conference on Current Trends in Theory and Practice of Computer Science, Nov'y Smokovec, Slovakia, January 26-29, 2014, Proceedings, 52--64.
• Alam, M. J., Kobourov, S. G., Liotta, G., Pupyrev, S., & Veeramoni, S. (2014). 3D proportional contact representations of graphs. In IISA 2014, The 5th International Conference on Information, Intelligence, Systems and Applications, Chania, Crete, Greece, July 7-9, 2014, 27--32.
• Alam, M. J., Kobourov, S. G., Pupyrev, S., & Toeniskoetter, J. (2014). Happy Edges: Threshold-Coloring of Regular Lattices. In Fun with Algorithms - 7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014. Proceedings, 28--39.
• Barth, L., Fabrikant, S. I., Kobourov, S. G., Lubiw, A., N"ollenburg, M., Okamoto, Y., Pupyrev, S., Squarcella, C., Ueckerdt, T., & Wolff, A. (2014). Semantic Word Cloud Representations: Hardness and Approximation Algorithms. In LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings, 514--525.
• Barth, L., Kobourov, S. G., & Pupyrev, S. (2014). Experimental Comparison of Semantic Word Clouds. In Experimental Algorithms - 13th International Symposium, SEA 2014, Copenhagen, Denmark, June 29 - July 1, 2014. Proceedings, 247--258.
• Bekos, M. A., Dijk, T. C., Fink, M., Kindermann, P., Kobourov, S. G., Pupyrev, S., Spoerhase, J., & Wolff, A. (2014). Improved Approximation Algorithms for Box Contact Representations. In Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, 87--99.
• Cruz, L. D., Kobourov, S. G., Pupyrev, S., Shen, P. S., & Veeramoni, S. (2014). Computing Consensus Curves. In Experimental Algorithms - 13th International Symposium, SEA 2014, Copenhagen, Denmark, June 29 - July 1, 2014. Proceedings, 223--234.
• Efrat, A., Hu, Y., Kobourov, S. G., & Pupyrev, S. (2014). MapSets: Visualizing Embedded and Clustered Graphs. In Graph Drawing - 22nd International Symposium, GD 2014, W"urzburg, Germany, September 24-26, 2014, Revised Selected Papers, 452--463.
• Fowler, J. J., Johnson, T., Simonetto, P., Schneider, M., Acedo, C., Kobourov, S. G., & Lazos, L. (2014). IMap: visualizing network activity over internet maps. In Proceedings of the Eleventh Workshop on Visualization for Cyber Security, Paris, France, November 10, 2014, 80--87.
• Fried, D., & Kobourov, S. G. (2014). Maps of Computer Science. In IEEE Pacific Visualization Symposium, PacificVis 2014, Yokohama, Japan, March 4-7, 2014, 113--120.
• Fried, D., Surdeanu, M., Kobourov, S. G., Hingle, M., & Bell, D. (2014). Analyzing the language of food on social media. In 2014 IEEE International Conference on Big Data, Big Data 2014, Washington, DC, USA, October 27-30, 2014, 778--783.
• Kobourov, S. G., Pupyrev, S., & Saket, B. (2014). Are Crossings Important for Drawing Large Graphs?. In Graph Drawing - 22nd International Symposium, GD 2014, W"urzburg, Germany, September 24-26, 2014, Revised Selected Papers, 234--245.
• Gansner, E. R., Hu, Y., Kobourov, S., North, S., Shen, H., & Vanwijk, J. (2008). GMap: Visualizing Graphs and Clusters as Maps. In IEEE PACIFIC VISUALIZATION SYMPOSIUM 2010, 201-208.
  More info

  Information visualization is essential in making sense out of large data sets. Often, high-dimensional data are visualized as a collection of points in 2-dimensional space through dimensionality reduction techniques. However, these traditional methods often do not capture well the underlying structural information, clustering, and neighborhoods. In this paper, we describe GMap, a practical algorithm for visualizing relational data with geographic-like maps. We illustrate the effectiveness of this approach with examples from several domains.
• Fowler, J. J., Kobourov, S. G., Hong, S., Nishizeki, T., & Quan, W. (2007). Minimum level nonplanar patterns for trees. In GRAPH DRAWING, 4875, 69-75.
  More info

  Minimum level nonplanar (MLNP) patterns play the role for level planar graphs that the forbidden Kuratowksi subdivisions K-5 and K-3,K-3 play for planar graphs. We add two MLNP patterns for trees to the previous set of tree patterns given by Healy et al. [4]. Neither of these patterns match any of the previous patterns. We show that this new set of patterns completely characterizes level planar trees.
• Duncan, C., Goodrich, M., Kobourov, S., , ., , ., & , . (2004). Balanced Aspect Ratio trees: Combining the advantages of k-d trees and octrees. In PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 300-309.
  More info

  Given a set S of n points in R(d), we show, for fixed d, how to construct in O(n log n) time a data structure we call the Balanced Aspect Ratio (BAR) tree. A. BAR tree is a binary space partition tree on S that has O(log n) depth and in which every region is convex and "fat" (that is, has a bounded aspect ratio). While previous hierarchical data structures, such as k-d trees, quadtrees, octrees, fair-split trees, and balanced box decompositions can guarantee some of these properties, we know of no previous data structure that combines all of these properties simultaneously The BAR tree data structure has numerous applications ranging from solving several geometric searching problems in fixed dimensional space to aiding in the visualization of graphs and three-dimensional worlds.
• Fowler, J. J., Kobourov, S. G., Hong, S., Nishizeki, T., & Quan, W. (2004). Characterization of unlabeled level planar graphs. In GRAPH DRAWING, 4875, 37-49.
  More info

  We present the set of planar graphs that always have a simultaneous geometric embedding with a strictly monotone path on the same set of n vertices, for any of the n! possible mappings. These graphs are equivalent to the set of unlabeled level planar (ULP) graphs that are level planar over all possible labelings. Our contributions are twofold. First, we provide linear time drawing algorithms for ULP graphs. Second, we provide a complete characterization of ULP graphs by showing that any other graph must contain a subgraph homeomorphic to one of seven forbidden graphs.
• Isaacman, S., Becker, R., Caceres, R., Kobourov, S., Martonosi, M., Rowland, J., Varshavsky, A., Lyons, K., Hightower, J., & Huang, E. (2004). Identifying Important Places in People's Lives from Cellular Network Data. In PERVASIVE COMPUTING, 6696, 133-151.
  More info

  People spend most of their time at a few key locations, such as home and work. Being able to identify how the movements of people cluster around these "important places" is crucial for a range of technology and policy decisions in areas such as telecommunications and transportation infrastructure deployment. In this paper, we propose new techniques based on clustering and regression for analyzing anonymized cellular network data to identify generally important locations, and to discern semantically meaningful locations such as home and work. Starting with temporally sparse and spatially coarse location information, we propose a new algorithm to identify important locations. We test this algorithm on arbitrary cellphone users, including those with low call rates, and find that we are within 3 miles of ground truth for 88% of volunteer users. Further, after locating home and work, we achieve commute distance estimates that are within 1 mile of equivalent estimates derived from government census data. Finally, we perform carbon footprint analyses on hundreds of thousands of anonymous users as an example of how our data and algorithms can form an accurate and efficient underpinning for policy and infrastructure studies.
• Brandes, U., Erten, C., Fowler, J., Frati, F., Geyer, M., Gutwenger, C., Hong, S., Kaufmann, M., Kobourov, S. G., Liotta, G., Mutzel, P., Symvonis, A., & Lin, G. (2001). Colored simultaneous geometric embeddings. In Computing and Combinatorics, Proceedings, 4598, 254-263.
  More info

  We introduce the concept of colored simultaneous geometric embeddings as a generalization of simultaneous graph embeddings with and without mapping. We show that there exists a universal pointset of size n for paths colored with two or three colors. We use these results to show that colored simultaneous geometric embeddings exist for: (1) a 2-colored tree together with any number of 2-colored paths and (2) a 2-colored outerplanar graph together with any number of 2-colored paths. We also show that there does not exist a universal pointset of size n for paths colored with five colors. We finally show that the following simultaneous embeddings are not possible: (1) three 6-colored cycles, (2) four 6-colored paths, and (3) three 9-colored paths.
• Duncan, C., Kobourov, S., Kumar, V., , ., , ., & , . (2001). Optimal constrained graph exploration. In PROCEEDINGS OF THE TWELFTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 807-814.
  More info

  We address the problem of exploring an unknown graph G = (17, E) from a given start node s with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. In both variations of the problem, the robot can only move along the edges of the graph, i.e, it cannot jump between non-adjacent vertices. In the tethered robot case, if the tether (rope) has length 1, then the robot must remain within distance I from the start node s. In the second variation, a fuel tank of limited capacity forces the robot to return to s after traversing C edges. Tile efficiency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. We present all algorithm for a tethered robot which explores the graph in 0(\E\) edge traversals. The problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a O(\E\) algorithm. This improves on the previous best known bound of O(\E\ + \V\ log(2) \V\) in [4]. Since the lower bound for the graph exploration problems is \E\, our algorithm is optimal, thus answering the open problem of Awerbuch, Betke, Rivest, and Singh [3].
• Estrella-Balderrama, A., Fowler, J. J., Kobourov, S. G., Kaufmann, M., & Wagner, D. (2001). Characterization of unlabeled level planar fees. In Graph Drawing, 4372, 367-379.
  More info

  Consider a graph G drawn in the plane so that each vertex lies on a distinct horizontal line l(j) = {(x, j) vertical bar x is an element of R}. The bijection phi that maps the set of n vertices V to a set of distinct horizontal lines l(j) forms a labeling of the vertices. Such a graph G with the labeling phi is called an n-level graph and is said to be n-level planar if it can be drawn with straight-line edges and no crossings while keeping each vertex on its own level. In this paper, we consider the class of trees that are n-level planar regardless of their labeling. We call such trees unlabeled level planar (ULP). Our contributions are three-fold. First, we provide a complete characterization of ULP trees in terms of a. pair of forbidden subtrees. Second, we show how to draw ULP trees in linear time. Third, we provide a linear time recognition algorithm for ULP trees.

Others

• Kobourov, S., & Kobourov, S. (2015). Canonical Orders and Schnyder Realizers. http://dx.doi.org/10.1007/978-3-642-27848-8_650-1