Stephen G Kobourov
 Professor, Computer Science
Contact
 (520) 6265320
 GouldSimpson, Rm. 715
 Tucson, AZ 85721
 kobourov@cs.arizona.edu
Degrees
 Ph.D. Computer Science
 Johns Hopkins University, Baltimore, Maryland, USA
 Visualizaton of Large Graphs
 M.S. Computer Science
 Johns Hopkins University, Baltimore, Maryland, USA
 B.S. Computer Science and Mathematics
 Dartmouth College, Hanover, New Hampshire, USA
Awards
 Best Paper Award
 27th International Symposium on Graph Drawing and Network Visualization, 2019, Fall 2019
 26th International Symposium on Graph Drawing and Network Visualization, 2018, Fall 2018
 13th International Conference and Workshops on Algorithms and Computation, 2018, Spring 2018
 25th International Symposium on Graph Drawing and Network Visualization, 2017, Fall 2017
 Keynote Lecture
 The IEEE VISSOFT 2019 conference, collocated with the IEEE ICSME 2019 conference in Cleveland, Ohio, USA., Fall 2019
 Most Influential Paper (MIP) award
 Most Influential Paper (MIP) award 2019 provided by the IEEE VISSOFT 2019 conference, Cleveland, Ohio, USA, Sept 30  Oct 1, 2019., Fall 2019
 Fulbright Distinguished Chair Award
 US Department of State, Spring 2016
 Distinguished Fulbright Chair
 United States Department of State, Fall 2015
 Humboldt Fellowship
 Alexander von Humboldt Foundation, Spring 2014
Interests
Teaching
Algorithms, Theory of Computing, Graph Theory, Information Visualization, Computational Geometry, Data Structures
Research
Design and analysis of algorithms, geometric algorithms, algorithm engineering, graph theory, information visualization, human computer interaction, graph drawing, and network visualization
Courses
202021 Courses

Dissertation
CSC 920 (Fall 2020) 
Theory Of Computation
CSC 573 (Fall 2020) 
Theory Of Computation
MATH 573 (Fall 2020)
201920 Courses

Adv Tpcs:Doctoral Colloq
CSC 695C (Spring 2020) 
Dissertation
CSC 920 (Spring 2020) 
Independent Study
CSC 399 (Spring 2020) 
Independent Study
CSC 599 (Spring 2020) 
Theory Of Computation
CSC 573 (Spring 2020) 
Theory Of Computation
MATH 573 (Spring 2020) 
Automata,Grammars+Lang
CSC 473 (Fall 2019) 
Research
CSC 900 (Fall 2019)
201819 Courses

Adv Tpcs:Doctoral Colloq
CSC 695C (Spring 2019) 
Honors Thesis
CSC 498H (Spring 2019) 
Theory Of Computation
CSC 573 (Spring 2019) 
Adv Tpcs:Doctoral Colloq
CSC 695C (Fall 2018) 
Honors Thesis
CSC 498H (Fall 2018)
201718 Courses

Adv Tpc Programming Lang
CSC 620 (Spring 2018) 
Adv Tpcs:Doctoral Colloq
CSC 695C (Spring 2018) 
Honors Thesis
CSC 498H (Spring 2018) 
Dsgn+Anls of Algorithms
CSC 545 (Fall 2017) 
Honors Thesis
CSC 498H (Fall 2017)
201617 Courses

Dissertation
CSC 920 (Spring 2017) 
Theory Of Computation
CSC 573 (Spring 2017) 
Theory Of Computation
MATH 573 (Spring 2017) 
Adv Tpcs:Doctoral Colloq
CSC 695C (Fall 2016) 
Dissertation
CSC 920 (Fall 2016) 
Dsgn+Anls of Algorithms
CSC 545 (Fall 2016)
201516 Courses

Adv Tpcs:Doctoral Colloq
CSC 695C (Spring 2016) 
Honors Thesis
CSC 498H (Spring 2016)
Scholarly Contributions
Chapters
 Kobourov, S. G. (2016). Canonical Orders and Schnyder Realizers. In Encyclopedia of Algorithms(pp 277283).
 Kobourov, S. G. (2015). Canonical Orders and Schnyder Realizers. In Encyclopedia of Algorithms(pp 18). Springer. doi:10.1007/9783642278488_6501
 Bl"asius, T., Kobourov, S. G., & Rutter, I. (2014). Simultaneous Embedding of Planar Graphs. In Handbook of Graph Drawing and Visualization(pp 349381). CRC Press.
 Kobourov, S. G. (2014). ForceDirected Drawing Algorithms. In Handbook of Graph Drawing and Visualization(pp 383408). CRC Press.
Journals/Publications
 Ahmed, A. R., Rahman, M. S., & Kobourov, S. (2019). Online facility assignment. Theoretical Computer Science.More infoThis 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). Multilevel Steiner trees. Journal of Experimental Algorithmics (JEA), 24(1), 122.More infoThis journal is ranked A in CORE
 Chen, H., Kobourov, S. G., Maciejewski, R., Lu, Y., Huroyan, V., & Soni, U. (2019). Same Stats, Different Graphs: Exploring the Space of Graphs in Terms of Graph Properties. IEEE transactions on visualization and computer graphics.More infoThis journal is ranked A in CORE
 Luca, F. D., Giacomo, E. D., Didimo, W., Kobourov, S. G., & Liotta, G. (2019). An Experimental Study on the Ply Number of Straightline Drawings. J. Graph Algorithms Appl., 23(1), 7191.
 Luca, F. D., Hossain, M. I., Kobourov, S. G., Lubiw, A., & Mondal, D. (2019). Recognition and drawing of stick graphs. Theor. Comput. Sci., 796, 2233.More infoThis journal is ranked A in CORE
 Okoe, M., Jianu, R., & Kobourov, S. G. (2019). NodeLink or Adjacency Matrices: Old Question, New Insights. IEEE Trans. Vis. Comput. Graph., 25(10), 29402952.More infoThis 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), 6787.
 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/s0045301702980More infoThis 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), 11701190.More infoThis 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 polyarc Lombardi drawings. JoCG, 9(1), 328355.
 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), 977994.More infoThis 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, 174185.
 Nusrat, S., Alam, M. J., & Kobourov, S. G. (2018). Evaluating Cartogram Effectiveness. IEEE Trans. Vis. Comput. Graph., 24(2), 10771090.More infoThis journal is ranked A in CORE
 Nusrat, S., Alam, M. J., Scheidegger, C., & Kobourov, S. G. (2018). Cartogram Visualization for Bivariate GeoStatistical Data. IEEE Trans. Vis. Comput. Graph., 24(10), 26752688.More infoThis journal is ranked A in CORE
 Okoe, M., Jianu, R., & Kobourov, S. G. (2018). Nodelink or Adjacency Matrices: Old Question, New Insights. IEEE transactions on visualization and computer graphics. doi:10.1109/TVCG.2018.2865940More infoThis 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), 672679.
 Simonetto, P., Archambault, D., & Kobourov, S. G. (2018). EventBased Dynamic Graph Visualisation. IEEE transactions on visualization and computer graphics. doi:10.1109/TVCG.2018.2886901More infoThis 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), 169181.
 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). Thresholdcoloring and unitcube contact representation of planar graphs. Discrete Applied Mathematics, 216, 214.
 Alam, M. J., Kobourov, S. G., & Mondal, D. (2016). Orthogonal Layout with Optimal Face Complexity. Computational Geometry: Theory and Applications, 63, 4052. 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, 4052.
 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). VertexColoring with Defects. J. Graph Algorithms Appl., 21(3), 313340.
 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), 902920.More infoThis journal is ranked A* in CORE.
 Bekos, M., Kobourov, S. G., Kaufmann, M., & Veeramoni, S. (2016). The Maximum kDifferential Coloring Problem. Journal of Discrete Algorithms, 45, 3553. doi:https://doi.org/10.1016/j.jda.2017.08.001
 Kobourov, S. G., Liotta, G., & Montecchiani, F. (2017). An annotated bibliography on 1planarity. Computer Science Review, 25, 4967.
 Kruiger, J. F., Rauber, P. E., Martins, R. M., Kerren, A., Kobourov, S. G., & Telea, A. (2017). Graph Layouts by tSNE. Comput. Graph. Forum, 36(3), 283294.
 Welch, E., & Kobourov, S. G. (2017). Measuring Symmetry in Drawings of Graphs. Computer Graphics Forum, 36(3), 341351.
 Alam, M. J., Chaplick, S., Fijavz, G., Kaufmann, M., Kobourov, S. G., Pupyrev, S., & Toeniskoetter, J. (2016). Thresholdcoloring and unitcube contact representation of planar graphs. DISCRETE APPLIED MATHEMATICS, 216, 214.
 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), 902920.More infoThis 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), 619642.
 Nusrat, S., Alam, M. J., & Kobourov, S. G. (2016). Evaluating Cartogram Effectiveness. IEEE Transacations on Visualization and Computer Graphics.More infoThis journal is ranked A* in CORE.
 Saket, B., Scheidegger, C., & Kobourov, S. (2016). Comparing NodeLink and NodeLinkGroup Visualizations From An Enjoyment Perspective. COMPUTER GRAPHICS FORUM, 35(3), 4150.
 Alam, M. J., Kaufmann, M., Kobourov, S. G., & Mchedlidze, T. (2015). Fitting Planar Graphs on Planar Maps. J. Graph Algorithms Appl., 19, 413440.
 Alam, M. J., Kobourov, S. G., & Veeramoni, S. (2015). Quantitative Measures for Cartogram Generation Techniques. Comput. Graph. Forum, 34, 351360.
 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, 233257.
 Das, A., Gansner, E. R., Kaufmann, M., Kobourov, S. G., Spoerhase, J., & Wolff, A. (2015). Approximating Minimum Manhattan Networks in Higher Dimensions. Algorithmica, 71, 3652.
 Efrat, A., Hu, Y., Kobourov, S. G., & Pupyrev, S. (2015). MapSets: Visualizing Embedded and Clustered Graphs. J. Graph Algorithms Appl., 19, 571593.
 Saket, B., Scheidegger, C., Kobourov, S. G., & B{"{o}}rner, K. (2015). Mapbased Visualizations Increase Recall Accuracy of Data. Comput. Graph. Forum, 34, 441450.
 Abello, J., Archambault, D., Kennedy, J., Kobourov, S., Ma, K. L., Miksch, S., Muelder, C., & Telea, A. (2014). Temporal multivariate networks. Multivariate Network Visualization, 151175.
 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, 5264.More infoAbstract: 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 NPhardness 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 nonconvex 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, 17.
 Bekos, M., Kaufmann, M., Kobourov, S., & Veeramoni, S. (2014). A note on maximum differential coloring of planar graphs. Journal of Discrete Algorithms, 29, 17.
 Saket, B., Simonetto, P., Kobourov, S. G., & B"orner, K. (2014). Node, NodeLink, and NodeLinkGroup Diagrams: An Evaluation. IEEE Trans. Vis. Comput. Graph., 20(12), 22312240.
 Yifan, H. u., Kobourov, S. G., & Veeramoni, S. (2014). Embedding, clustering and coloring for dynamic maps. Journal of Graph Algorithms and Applications, 18(1), 77109.More infoAbstract: 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 4connected planar graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7704 LNCS, 211223.More infoAbstract: In a contact representation of a planar graph, vertices are represented by interiordisjoint polygons and two polygons share a nonempty 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 4connected 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 10year old conjecture on the existence of a Hamiltonian canonical cycle in a 4connected 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 NPhard to decide whether a 4connected planar graph admits a proportional contact representation using only rectangles. © 2013 SpringerVerlag.
 Alam, M. J., Biedl, T., Felsner, S., Gerasch, A., Kaufmann, M., & Kobourov, S. G. (2013). Lineartime algorithms for holefree rectilinear proportional contact graph representations. Algorithmica, 67(1), 322.More infoAbstract: 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 12sided rectilinear polygons and takes O(nlogn) time. We describe a new algorithm that guarantees 10sided rectilinear polygons and runs in O(n) time. We also describe a lineartime algorithm for proportional contact representation of planar 3trees with 8sided rectilinear polygons and show that this is optimal, as there exist planar 3trees that require 8sided polygons. We then show that a maximal outerplanar graph admits a proportional contact representation using rectilinear polygons with 6 sides when the outerboundary is a rectangle and with 4 sides otherwise. Finally we study maximal seriesparallel graphs. Here we show that O(1)sided rectilinear polygons are not possible unless we allow holes, but 6sided 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), 784810.More infoAbstract: In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by sidecontact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a prespecified 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 8sided polygons, which is optimal in terms of polygonal complexity as 8sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an areauniversal rectangular layout in linear time. The exact cartogram can be computed from the areauniversal layout with numerical iteration, or can be approximated with a hillclimbing 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 8sided rectilinear polygons are necessary, by constructing a nontrivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is onelegged, as in outerplanar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outerplanar graphs. Finally we address the problem of constructing smallcomplexity cartograms for 4connected graphs (which are Hamiltonian). We first disprove a conjecture, posed by two set of authors, that any 4connected maximal planar graph has a onelegged Hamiltonian cycle, thereby invalidating an attempt to achieve a polygonal complexity 6 in cartograms for this graph class. We also prove that it is NPhard to decide whether a given 4connected 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). Straightline grid drawings of 3connected 1planar graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8242 LNCS, 8394.More infoAbstract: A graph is 1planar if it can be drawn in the plane such that each edge is crossed at most once. In general, 1planar graphs do not admit straightline drawings. We show that every 3connected 1planar graph has a straightline 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 1planar 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, 125.More infoAbstract: 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 n10 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 embeddingpreserving monotone drawings with straightline edges. In fact, we prove that biconnected embedded planar graphs and outerplane graphs always admit such drawings, and describe lineartime 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), 575595.More infoAbstract: 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 axisaligned line segments, in smooth orthogonal layouts every edge is made of axisaligned 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 4planar graph has a smooth orthogonal layout with edge complexity 3. If the input graph has a complexity2 traditional orthogonal layout, we can transform it into a smooth complexity2 layout. Using the Kandinsky model for removing the degree restriction, we show that any planar graph has a smooth complexity2 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, 150161.More infoAbstract: 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 axisaligned line segments, in smooth orthogonal layouts every edge is made of axisaligned 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 4planar graph has a smooth orthogonal layout with edge complexity 3. If the input graph has a complexity2 traditional orthogonal layout, we can transform it into a smooth complexity2 layout. Using the Kandinsky model for removing the degree restriction, we show that any planar graph has a smooth complexity2 layout. © 2013 SpringerVerlag.
 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, 187198.More infoAbstract: We consider contact representations of graphs where vertices are represented by cuboids, i.e. interiordisjoint axisaligned 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 nonzero 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 axisaligned 3D boxes. We prove that it is NPcomplete 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 SpringerVerlag.
 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, 722732.More infoAbstract: 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 minimumlength rectilinear network that connects every pair in R by a Manhattan path, that is, a path of axisparallel 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 wellknown rectilinear Steiner arborescence problem (RSA). As a generalization of these problems, GMMN is NPhard. 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 2DRSA generalizes to higher dimensions. © 2013 SpringerVerlag.
 Das, A., Gansner, E. R., Kaufmann, M., Kobourov, S., Spoerhase, J., & Wolff, A. (2013). Approximating Minimum Manhattan Networks in Higher Dimensions. Algorithmica, 117.More infoAbstract: We study the minimum Manhattan network problem, which is defined as follows. Given a set of points called terminals in {Mathematical expression}, find a minimumlength network such that each pair of terminals is connected by a set of axisparallel line segments whose total length is equal to the pair's Manhattan (that is, L1) distance. The problem is NPhard 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(k1)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), 157182.More infoAbstract: 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 crossingfree straightline drawing with perfect angular resolution and polynomial area. 2. There are ordered trees that require exponential area for any crossingfree straightline drawing having perfect angular resolution. 3. Any ordered tree has a crossingfree Lombardistyle 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 straightline drawings and what more is achievable with Lombardistyle 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, 421432.More infoAbstract: A table cartogram of a two dimensional m × n table A of nonnegative 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 SpringerVerlag.
 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, 388399.More infoAbstract: Spring embedders are conceptually simple and produce straightline 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 nonplane drawings, as edge crossings do not factor into the objective function being minimized. On the other hand, there are fairly straightforward algorithms for creating plane straightline 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 SpringerVerlag.
 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), 898899.
 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 infoPMID: 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 dietrelated 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 9item exit survey. Participant data were captured from the public Twitter stream, and frequency of hashtag occurrence and cooccurrence were determined. Contextual data were further parsed and qualitatively analyzed. A frequency matrix was constructed to identify food and behavior hashtags that cooccurred. 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 studyprovided hash tags and their own hash tags to describe behavior. Most rated Twitter as easy to use for the purpose of reporting dietrelated behavior. "Maps" of hash tag occurrences and cooccurrences were developed that suggested timevarying diet and behavior patterns. Conclusions: Twitter combined with an analytical software tool provides a method for capturing realtime food consumption and dietrelated 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 foodrelated 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 3connected planar graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7704 LNCS, 199210.More infoAbstract: 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 3connected 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 fixedparameter tractable decision algorithm for testing whether a 3connected planar graph admits a proper TTG representation. © 2013 SpringerVerlag.
 Kobourov, S., Ueckerdt, T., & Verbeek, K. (2013). Combinatorial and geometric properties of planar Laman graphs. Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms, 16681678.More infoAbstract: Laman graphs naturally arise in structural mechanics and rigidity theory. Specifically, they characterize minimally rigid planar barandjoint 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 Lcontact representation, that is, planar Laman graphs are contact graphs of axisaligned Lshapes. 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 Lcontact representation of G. The overall running time is Script O sign(n 2), where n is the number of vertices of G, and the Lcontact representation is realized on the n x n grid. Copyright © SIAM.
 Kämper, J., Kobourov, S. G., & Nollenburg, M. (2013). Circulararc cartograms. IEEE Pacific Visualization Symposium, 18.More infoAbstract: We present a new circulararc cartogram model in which countries are drawn as polygons with circular arcs instead of straightline 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 circulararc cartogram model straightline 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 circulararc 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 areavalues can be realized as a circulararc cartogram is an NPhard problem. Next we describe a heuristic method for constructing circulararc cartograms, which uses a maxflow 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 realworld 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, 451462.More infoAbstract: A recent line of work in graph drawing studies Lombardi drawings, i.e., drawings with circulararc 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 nearLombardi forcebased 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 SpringerVerlag.
 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), 701728.More infoAbstract: We study contact representations for planar graphs, with vertices rep resented by simple polygons and adjacencies represented by pointcontacts or sidecontacts between the corresponding polygons. Specifically, we consider proportional contact representations, where prespecified 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 2segment graphs, which include maximal outerplanar graphs and partial 2trees.
 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, 2638.More infoAbstract: We study contact representations for planar graphs, with vertices represented by simple polygons and adjacencies represented by pointcontacts or sidecontacts between the corresponding polygons. Specifically, we consider proportional contact representations, where prespecified 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 2segment graphs, which include maximal outerplanar graphs and partial 2trees. © 2012 SpringerVerlag 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, 2130.More infoAbstract: In a rectilinear dual of a planar graph vertices are represented by simple rectilinear polygons, while edges are represented by sidecontact between the corresponding polygons. A rectilinear dual is called a cartogram if the area of each region is equal to a prespecified 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 8sided polygons, which is optimal in terms of polygonal complexity as 8sided polygons are sometimes necessary. Specifically, we show how to compute the combinatorial structure and how to refine it into an areauniversal rectangular layout in linear time. The exact cartogram can be computed from the areauniversal layout with numerical iteration, or can be approximated with a hillclimbing 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 8sided rectilinear polygons are necessary, by constructing a nontrivial lower bound example. The complexity of the cartograms can be reduced to 6 if the Hamiltonian path has the extra property that it is onelegged, as in outerplanar graphs. Thus, we have optimal representations (in terms of both polygonal complexity and running time) for Hamiltonian maximal planar and maximal outerplanar 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, 379390.More infoAbstract: 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 embeddingpreserving monotone drawings with straightline edges, and we show that biconnected embedded planar graphs and outerplane graphs always admit such drawings, which can be computed in linear time. © 2012 SpringerVerlag Berlin Heidelberg.
 Chernobelskiy, R., Cunningham, K. I., Goodrich, M. T., Kobourov, S. G., & Trott, L. (2012). Forcedirected Lombardistyle graph drawing. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7034 LNCS, 320331.More infoAbstract: 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 "Lombardistyle" drawings (which we also call nearLombardi drawings), in which all edges are still circular arcs, but some vertices may not have perfect angular resolution. Both of these algorithms take a forcedirected, springembedding 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 nearLombardi drawings, with one being slightly better at achieving nearperfect angular resolution and the other being slightly better at balancing edge placements. © 2012 SpringerVerlag Berlin Heidelberg.
 Duncan, C. A., Eppstein, D., Goodrich, M. T., Kobourov, S. G., & Löffler, M. (2012). Planar and polyarc Lombardi drawings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7034 LNCS, 308319.More infoAbstract: 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 kLombardi drawings, in which each edge may be drawn with k circular arcs, noting that every graph has a smooth 2Lombardi drawing. We show that every planar graph has a smooth planar 3Lombardi drawing and further investigate topics connecting planarity and Lombardi drawings. © 2012 SpringerVerlag 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), 85108.More infoAbstract: 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), 14241437.More infoAbstract: 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 heatmap overlays. In this paper, we consider visualizing largescale dynamic relational data by taking advantage of the geographic map metaphor. We describe a mapbased 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 TVviewing patterns from an IPTV service. All map images in this paper are available in highresolution 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, 3340.More infoAbstract: 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). Lineartime algorithms for holefree rectilinear proportional contact graph representations. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7074 LNCS, 281291.More infoAbstract: 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 12sided rectilinear polygons and takes O(nlogn) time. We describe a new algorithm that guarantees 10sided rectilinear polygons and runs in O(n) time. We also describe a lineartime algorithm for proportional contact representation of planar 3trees with 8sided rectilinear polygons and show that this is optimal, as there exist planar 3trees that require 8sided polygons. Finally, we show that a maximal outerplanar graph admits a proportional contact representation using rectilinear polygons with 6 sides when the outerboundary is a rectangle and with 4 sides otherwise. © 2011 SpringerVerlag.
 Biedl, T., Dernaine, E., Duncan, C., Fleischer, R., & Kobourov, S. (2011). Tight bounds on maximal and maximum matchings. DISCRETE MATHEMATICS, 285(13), 715.More infoIn this paper, we study lower bounds on the size of maximal and maximum matchings in 3connected 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., EstrellaBalderrama, 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), 569592.More infoAbstract: 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 kcolored 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, 4960.More infoAbstract: We consider the minimum Manhattan network problem, which is defined as follows. Given a set of points called terminals in ℝd , find a minimumlength network such that each pair of terminals is connected by a set of axisparallel line segments whose total length is equal to the pair's Manhattan (that is, L 1) distance. The problem is NPhard 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(k1)approximation for the case that the terminals are contained in the union of κ≥2 parallel planes. © 2011 SpringerVerlag 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, 177182.More infoAbstract: For a set S of n lines labeled from 1 to n, we say that S supports an nvertex planar graph G if for every labeling from 1 to n of its vertices, G has a straightline crossingfree 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 nvertex 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 nvertex planar graphs. Finally, we show that there exists a set of n lines in general position that does not support all nvertex planar graphs. © 2011 SpringerVerlag.
 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, 183194.More infoAbstract: 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 crossingfree straightline drawing with perfect angular resolution and polynomial area. 2 There are ordered trees that require exponential area for any crossingfree straightline drawing having perfect angular resolution. 3 Any ordered tree has a crossingfree Lombardistyle 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 straightline drawings and what more is achievable with Lombardistyle drawings, with respect to drawings of trees with perfect angular resolution. © 2011 SpringerVerlag.
 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, 195207.More infoAbstract: 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 SpringerVerlag.
 Duncan, C. A., Gansner, E. R., Hu, Y. F., Kaufmann, M., & Kobourov, S. G. (2011). Optimal Polygonal Representation of Planar Graphs. Algorithmica (New York), 120.More infoAbstract: 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 lineartime 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 highergenus graphs. Journal of Graph Algorithms and Applications, 15(1), 732.More infoAbstract: In this paper, we give polynomialtime 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 highergenus 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 NPcomplete to determine whether a given graph embedded in a genusg surface has a set of 2g fundamental cycles with vertexdisjoint interiors, which would be desirable from a graphdrawing 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), 385398.More infoAbstract: 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 onetoone 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, 250261.More infoAbstract: 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 SpringerVerlag.
 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, 8893.More infoAbstract: 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, 133151.More infoAbstract: 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 SpringerVerlag.
 Mashima, D., Kobourov, S. G., & Yifan, H. u. (2011). Visualizing dynamic data with maps. IEEE Pacific Visualization Symposium 2011, PacificVis 2011  Proceedings, 155162.More infoAbstract: 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 heatmap overlays. In this paper we consider visualizing largescale 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 mapbased 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, 274286.More infoAbstract: 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 kHamiltonian path. As computing the maximum differential coloring is NPComplete, we describe an exact backtracking algorithm and a spectralbased heuristic. We also discuss lower bounds and upper bounds for the differential chromatic number for several classes of graphs. © 2011 SpringerVerlag.
 Binucci, C., Di Giacomo, E., Didimo, W., EstrellaBalderrama, A., Frati, F., Kobourov, S. G., & Liotta, G. (2010). Upward straightline embeddings of directed graphs into point sets. COMPUTATIONAL GEOMETRYTHEORY AND APPLICATIONS, 43(2), 219232.More infoIn this paper we study the problem of computing an upward straightline 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 straightline segment, and all the edges are oriented according to a common direction. In particular, we show that no biconnected DAG admits an upward straightline embedding into every point set in convex position. We provide a characterization of the family of DAGs that admit an upward straightline embedding into every convex point set such that the points with the largest and the smallest ycoordinate 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 straightline 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 straightline 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 subclasses 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., EstrellaBalderrama, A., Frati, F., Kobourov, S. G., & Liotta, G. (2010). Upward straightline embeddings of directed graphs into point sets. Computational Geometry: Theory and Applications, 43(2 SPEC. ISS.), 219232.More infoAbstract: In this paper we study the problem of computing an upward straightline 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 straightline segment, and all the edges are oriented according to a common direction. In particular, we show that no biconnected DAG admits an upward straightline embedding into every point set in convex position. We provide a characterization of the family of DAGs that admit an upward straightline embedding into every convex point set such that the points with the largest and the smallest ycoordinate 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 straightline 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 straightline 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 subclasses 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). MSDRD network localization algorithm. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 6451 LNCS, 148160.More infoAbstract: We present a distributed multiscale deadreckoning (MSDRD) algorithm for network localization that utilizes local distance and angular information for nearby sensors. The algorithm is anchorfree 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://msdrd.cs. arizona.edu/. © 2010 SpringerVerlag.
 Duncan, C. A., Goodrich, M. T., & Kobourov, S. G. (2010). Planar drawings of highergenus graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5849 LNCS, 4556.More infoAbstract: In this paper, we give polynomialtime 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 highergenus graphs in the plane. As a side note, we show that it is NPcomplete to determine whether a given graph embedded in a genusg surface has a set of 2g fundamental cycles with vertexdisjoint interiors, which would be desirable from a graphdrawing perspective. © 2010 SpringerVerlag.
 Erten, C., Kobourov, S., Le, ., Navabi, A., & Liotta, G. (2010). Simultaneous graph drawing: Layout algorithms and visualization schemes. GRAPH DRAWING, 2912, 437449.More infoIn 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 forcedirected 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.
 EstrellaBalderrama, A., Fowler, J. J., & Kobourov, S. G. (2010). GraphSET, a tool for simultaneous graph drawing. Software  Practice and Experience, 40(10), 849863.More infoAbstract: 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 builtin 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.
 EstrellaBalderrama, 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, 6980.More infoAbstract: 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 nonplanar (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 SpringerVerlag.
 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, 417432.More infoAbstract: 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 SpringerVerlag.
 Gansner, E. R., Yifan, H. u., & Kobourov, S. (2010). GMap: Visualizing graphs and clusters as maps. IEEE Pacific Visualization Symposium 2010, PacificVis 2010  Proceedings, 201208.More infoAbstract: Information visualization is essential in making sense out of large data sets. Often, highdimensional data are visualized as a collection of points in 2dimensional 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 geographiclike 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, 405407.
 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, 1924.More infoAbstract: 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), 5466.More infoAbstract: Information visualization is essential in making sense of large datasets. Often, highdimensional 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 geographiclike 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). Thresholdcoloring and unitcube contact representation of graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8165 LNCS, 2637.More infoAbstract: 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 thresholdcolorable, but several subclasses, such as trees, some planar grids, and planar graphs with no short cycles can always be thresholdcolored. Using these results we obtain unitcube contact representation of several subclasses of planar graphs. We show the NPcompleteness for two variants of the threshold coloring problem and describe a polynomialtime algorithm for another. © 2013 SpringerVerlag.
 Binucci, C., Giacomo, E. D., Didimo, W., EstrellaBalderrama, A., Frati, F., Kobourov, S. G., & Liotta, G. (2009). On directed graphs with an upward straightline embedding into every point set. Proceedings of the 21st Annual Canadian Conference on Computational Geometry, CCCG 2009, 2124.More infoAbstract: In this paper we study the problem of computing an up ward straightline 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 straightline segment, and all the edges are oriented according to a common direction. We characterize the family of directed graphs that admit an upward straightline embedding into every oneside convex point set, that is, into every pointset such that the topmost and the bottommost points are adjacent in the convex hull of the point set. Also we show how to construct up ward straightline embeddings for a subclass of directed paths when the point set is in general position.
 Cappos, J., EstrellaBalderrama, A., Fowler, J. J., & Kobourov, S. G. (2009). Simultaneous graph embedding with bends and circular arcs. Computational Geometry: Theory and Applications, 42(2), 173182.More infoAbstract: A simultaneous embedding of two vertexlabeled 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 nlevel 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 starshaped levels to find 2bends 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 Lcontact graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 8165 LNCS, 139151.More infoAbstract: We consider Lgraphs, that is contact graphs of axisaligned Lshapes in the plane, all with the same rotation. We provide several characterizations of Lgraphs, 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 squarebased cuboids. We also study a slightly more restricted version of equilateral Lcontact 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 SpringerVerlag.
 Duncan, C., Goodrich, M., & Kobourov, S. (2009). Balanced aspect ratio trees: Combining the advantages of kd trees and octrees. JOURNAL OF ALGORITHMSCOGNITION INFORMATICS AND LOGIC, 38(1), 303333.More infoGiven 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 kd trees, quadtrees, octrees, fairsplit 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 threedimensional worlds, (C) 2001 Academic Press.
 EstrellaBalderrama, A., Fowler, J. J., & Kobourov, S. G. (2009). Characterization of unlabeled level planar trees. Computational Geometry: Theory and Applications, 42(67), 704721.More infoAbstract: 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 ycoordinate of all vertices match their labels and edges are drawn strictly ymonotone, 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 lineartime 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 lineartime recognition algorithm for ULP trees. © 2009 Elsevier B.V. All rights reserved.
 EstrellaBalderrama, 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, 1720.More infoAbstract: A set of n points in the plane is a universal pointset for a given class of graphs, if any nvertex 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 kcolored points in the plane such that each vertex can be mapped to a point of the same color, resulting in a straightline plane drawing of each graph. We consider classes of trees and show that there exist universal or near universal pointsets for 3colored cater pillars, 3colored radius2 stars, and 2colored spiders.
 EstrellaBalderrama, 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, 169180.More infoAbstract: 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 builtin 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 nearsimultaneous embeddings. Journal of Graph Algorithms and Applications, 13(3), 447465.More infoAbstract: 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 straightline 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 nearsimultaneous 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, 345348.More infoAbstract: 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 2Dembeddings 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, 395400.More infoAbstract: 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 graphdrawing technology. © 2008 SpringerVerlag Berlin Heidelberg.
 EstrellaBalderrama, A., Frati, F., & Kobourov, S. G. (2008). Upward straightline 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, 122133.More infoAbstract: In this paper we consider the problem of characterizing the directed graphs that admit an upward straightline embedding into every point set in convex or in general position. In particular, we show that no biconnected directed graph admits an upward straightline embedding into every point set in convex position, and we provide a characterization of the Hamiltonian directed graphs that admit upward straightline embeddings into every point set in general or in convex position. We also describe how to construct upward straightline 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 NPhard. © 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, 3749.More infoAbstract: 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 SpringerVerlag 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, 6975.More infoAbstract: 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 SpringerVerlag 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), 4144.More infoAbstract: 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, 146158.More infoAbstract: 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 lineartime 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 nearsimultaneous embeddings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4875 LNCS, 268279.More infoAbstract: 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 straightline 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 nearsimultaneous embedding problem, in which vertices are not mapped exactly to the same but to "near" points in the different drawings. © 2008 SpringerVerlag Berlin Heidelberg.
 Gajer, P., Goodrich, M., & Kobourov, S. (2008). A multidimensional approach to forcedirected layouts of large graphs. COMPUTATIONAL GEOMETRYTHEORY AND APPLICATIONS, 29(1), 318.More infoWe present a novel hierarchical forcedirected 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 higherdimensional 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), 113127.More infoAbstract: We consider the problem of intersectionfree planar graph morphing, and in particular, a generalization from Euclidean space to spherical space. We show that there exists a continuous and intersectionfree 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: intersectionfree geodesicarc 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, 515539.More infoIn 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, 254263.More infoAbstract: 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 2colored tree together with any number of 2colored paths and (2) a 2colored outerplanar graph together with any number of 2colored 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 6colored cycles, (2) four 6colored paths, and (3) three 9colored paths. © SpringerVerlag Berlin Heidelberg 2007.
 Cappos, J., EstrellaBalderrama, 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, 95107.More infoAbstract: We consider the problem of simultaneous embedding of planar graphs. We demonstrate how to simultaneously embed a path and an nlevel 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 starshaped levels to find 2bends per path edge simultaneous embeddings of a path and an outerplanar graph. All embedding algorithms run in O(n) time. © SpringerVerlag 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), 11431163.More infoTraditionally, 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). Graphdrawing contest report. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4372 LNCS, 448452.More infoAbstract: 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 graphdrawing technology. © SpringerVerlag Berlin Heidelberg 2007.
 EstrellaBalderrama, 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, 367379.More infoAbstract: 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 nlevel graph and is said to be nlevel planar if it can be drawn with straightline edges and no crossings while keeping each vertex on its own level. In this paper, we consider the class of trees that are nlevel planar regardless of their labeling. We call such trees unlabeled level planar (ULP). Our contributions are threefold. 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. © SpringerVerlag 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, 306317.More infoAbstract: We consider the problem of intersectionfree planar graph morphing, and in particular, a generalization from Euclidean space to spherical space. We show that there exists a continuous and intersectionfree 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: intersectionfree geodesicarc 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. © SpringerVerlag Berlin Heidelberg 2007.
 Cheng, C., Duncan, C., Goodrich, M., Kobourov, S., & Kratochvil, J. (2006). Drawing planar graphs with circular arcs. GRAPH DRAWING, 1731, 117126.More infoIn 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 nvertex 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 straightline 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), 380402.More infoAbstract: 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 bestknown 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). Graphdrawing contest report. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 3843 LNCS, 528531.More infoAbstract: 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 graphdrawing technology. © SpringerVerlag Berlin Heidelberg 2005.
 EstrellaBalderrama, A., Fowler, J. J., & Kobourov, S. G. (2006). Characterization of unlabeled level planar trees. COMPUTATIONAL GEOMETRYTHEORY AND APPLICATIONS, 42(67), 704721.More infoConsider 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 ycoordinate of all vertices match their labels and edges are drawn strictly ymonotone. 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 lineartime 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 lineartime 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 ACMSIAM Symposium on Discrete Algorithms: Preface. Proceedings of the Annual ACMSIAM 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), 405418.More infoIn 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 nvertex 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 straightline segments. Finally, we show how to create drawings in which edges are smooth C1continuous 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), 313327.More infoAbstract: 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 straightline segments and the only crossings are between primal  dual pairs of edges. We provide an O(n) time algorithm that simultaneously embeds a 3connected 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 straightline 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), 347364.More infoAbstract: 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 crossingsfree, 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 fixededges. 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 treepath pairs with at most one bend per treeedge 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, 98110.More infoGraphAEL 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), 165182.More infoAbstract: 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 forcedirected 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). NonEuclidean spring embedders. IEEE Transactions on Visualization and Computer Graphics, 11(6), 757767.More infoPMID: 16270867;Abstract: We present a conceptually simple approach to generalizing forcedirected methods for graph layout from Euclidean geometry to Riemannian geometries. Unlike previous work on nonEuclidean forcedirected 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 forceinteractions to smooth nonEuclidean 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 nonEuclidean 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, 986989.More infoAbstract: We study the performance of collaborative spatial/visual tasks under different input configurations. The configurations used are a traditional mousemonitor, a sharedmonitor with multiplemice, and a multiuser 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 wellsuited for collaborative tasks, and even after augmenting it to a shared monitor with multiplemice it is still significantly inferior to the multiuser input device. © IFIP International Federation for Information Processing 2005.
 Abello, J., Kobourov, S. G., & Yusufov, R. (2004). Visualizing large graphs with compoundfisheye views and treemaps. Lecture Notes in Computer Science, 3383, 431441.More infoAbstract: Compoundfisheye views are introduced as a method for the display and interaction with large graphs. The method relies on a hierarchical clustering of the graph, and a generalization of the traditional fisheye view, together with a treemap representation of the cluster tree. © SpringerVerlag 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(13), 715.More infoAbstract: In this paper, we study lower bounds on the size of maximal and maximum matchings in 3connected 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). Graphdrawing contest report. Lecture Notes in Computer Science, 3383, 512516.More infoAbstract: 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 graphdrawing technology. © SpringerVerlag 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, 515539.More infoAbstract: 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. © SpringerVerlag 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 GEOMETRYTHEORY AND APPLICATIONS, 36(2), 117130.More infoWe 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, 340346.More infoAbstract: 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 GEOMETRYTHEORY AND APPLICATIONS, 35(3), 162172.More infoWe 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, 195205.More infoAbstract: 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 fixededges for treepath pairs on the O(n) × O(n 2) grid with at most one bend per treeedge and no bends along path edges. © SpringerVerlag 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, 4556.More infoAbstract: 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 twodimensional 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, 98110.More infoAbstract: 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. © SpringerVerlag 2004.
 Erten, C., Kobourov, S. G., & Pitta, C. (2004). Intersectionfree morphing of planar graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2912, 320331.More infoAbstract: 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 intersectionfree 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 straightline segments, bends, and curves. Our system is implemented in Java and available as an applet at http://gmorph.cs.arizona.edu. © SpringerVerlag 2004.
 Erten, C., Kobourov, S. G., & Pitta, C. (2004). Morphing planar graphs. Proceedings of the Annual Symposium on Computational Geometry, 451452.More infoAbstract: 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 barycentricrepresentation 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, 437449.More infoAbstract: 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 forcedirected 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/. © SpringerVerlag 2004.
 Erten, C., Kobourov, S., & Pach, J. (2004). Simultaneous embedding of planar graphs with few bends. GRAPH DRAWING, 3383, 195205.More infoWe 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 fixededges for treepath pairs on the O(n) x O(n(2)) grid with at most one bend per treeedge and no bends along path edges.
 Forrester, D., Kobourov, S. G., Navabi, A., Wampler, K., & Yee, G. V. (2004). Graphael: A system for generalized forcedirected layouts. Lecture Notes in Computer Science, 3383, 454464.More infoAbstract: The graphael system implements several traditional forcedirected layout methods, as well as several novel layout methods for nonEuclidean geometries, including hyperbolic and spherical. The system can handle large graphs, using multiscale 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. © SpringerVerlag Berlin Heidelberg 2004.
 Gajer, P., Goodrich, M. T., & Kobourov, S. G. (2004). A multidimensional approach to forcedirected layouts of large graphs. Computational Geometry: Theory and Applications, 29(1), 318.More infoAbstract: We present a novel hierarchical forcedirected 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 higherdimensional 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 multiscale technique based on a maximal independent set filtration of vertices of the graph. While most existing forcedirected 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 multiuser system for simultaneous graph drawing. Lecture Notes in Computer Science, 3383, 492501.More infoAbstract: 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, touchsensitive 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. © SpringerVerlag Berlin Heidelberg 2004.
 Kobourov, S. G., & Wampler, K. (2004). Noneuclidean spring embedders. Proceedings  IEEE Symposium on Information Visualization, INFO VIS, 207214.More infoAbstract: We present a method by which forcedirected 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 forceinteractions to smooth nonEuclidean 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 multiuser system for simultaneous graph drawing. GRAPH DRAWING, 3383, 492501.More infoIn 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, touchsensitive 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), 311333.More infoAbstract: 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, bendpoint 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 bendpoint 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 bendpoint 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). Planaritypreserving clustering and embedding for large planar graphs. Computational Geometry: Theory and Applications, 24(2), 95114.More infoAbstract: In this paper we present a novel approach for clusterbased drawing of large planar graphs that maintains planarity. Our technique works for arbitrary planar graphs and produces a clustering which satisfies the conditions for compoundplanarity (cplanarity). 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, 407421.More infoAbstract: 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, bendpoint 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, bendpoint 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 bendpoint 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 bendpoint resolution and √2/2 edge separation), the PRA algorithm creates a drawing of size 9n × 9n/2. © SpringerVerlag 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, 575587.More infoAbstract: 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 straightline segments and the only crossings are between primaldual pairs of edges. We provide an O(n) time algorithm that simultaneously embeds a 3connected 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. © SpringerVerlag Berlin Heidelberg 2002.
 Gajer, P., & Kobourov, S. G. (2002). GRIP: Graph Drawing with Intelligent Placement. Journal of Graph Algorithms and Applications, 6(3), 203224.More infoAbstract: This paper describes a system for Graph dRawing with Intelligent Placement, GRIP. The system is designed for drawing large graphs and uses a novel multidimensional forcedirected 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 midrange 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, 308319.More infoAbstract: 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), 405418.More infoAbstract: 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 nvertex 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 straightline segments. Finally, we show how to create drawings in which edges are smooth C1continuous 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 kd Trees and Octrees. Journal of Algorithms, 38(1), 303333.More infoAbstract: 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 kd trees, quadtrees, octrees, fairsplit 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 threedimensional worlds. © 2001 Academic Press.
 Duncan, C. A., Kobourov, S. G., & Kumar, V. A. (2001). Optimal constrained graph exploration. Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms, 807814.More infoAbstract: 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 nonadjacent 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 + \V2log 2V) 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), 139143.More infoAbstract: We describe a Webbased 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 _{E}X. SIGCSE Bulletin (Association for Computing Machinery, Special Interest Group on Computer Science Education), 300304.More infoAbstract: 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 online 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), 1946.More infoAbstract: We describe a new approach for clusterbased drawing of large graphs, which obtains clusters by using binary space partition (BSP) trees. We also introduce a novel BSPtype 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), 8894.
 Duncan, C. A., Goodrich, M. T., & Kobourov, S. (1999). Balanced aspect ratio trees: Combining the advantages of kd trees and octrees. Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms, 300309.More infoAbstract: 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 kd trees, quadtrees, octrees, fairsplit 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 threedimensional worlds.
 Kobourov, S., & Wampler, K. (1999). NonEuclidean spring embedders. IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, 11(6), 757767.More infoWe present a conceptually simple approach to generalizing forcedirected methods for graph layout from Euclidean geometry to Riemannian geometries. Unlike previous work on nonEuclidean forcedirected 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 forceinteractions to smooth nonEuclidean 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 nonEuclidean geometries.
 Awerbuch, B., & Kobourov, S. G. (1998). Polylogarithmicoverhead piecemeal graph exploration. Proceedings of the Annual ACM Conference on Computational Learning Theory, 280286.More infoAbstract: 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 nonadjacent 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 breadthfirst and depthfirst 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., Hamm, K., Jebelli, M., Kobourov, S. G., Sahneh, F. D., & Spence, R. (2019). Approximation Algorithms and an Integer Program for Multilevel Graph Spanners. In Analysis of Experimental Algorithms  Special Event, SEA\({^2\)} 2019, Kalamata, Greece, June 2429, 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 1720, 2019, Proceedings.More infoThis 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 1planar 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). StressPlusX (SPX) Graph Layout. In Graph Drawing and Network Visualization  27th International Symposium, GD 2019, Prague, Czech Republic, September 1720, 2019, Proceedings.More infoThis 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 1720, 2019, Proceedings.More infoThis 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 NearestNeighbor Chains: Euclidean TSP and Motorcycle Graphs. In 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 811, 2019, Shanghai University of Finance and Economics, Shanghai, China.More infoThis 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 1720, 2019, Proceedings.More infoThis 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). MultiLevel Steiner Trees. In 17th International Symposium on Experimental Algorithms, SEA 2018, June 2729, 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 35, 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 2628, 2018, Proceedings.More infoThis 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 2628, 2018, Proceedings.More infoThis 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 1719, 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 2628, 2018, Proceedings.More infoThis 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 2628, 2018, Proceedings.More infoThis 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 2527, 2017, Revised Selected Papers.More infoThis 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 EmptyPly Proximity Drawings. In Symposium on Graph Drawing and Network Visualization, 2437.More infoThis 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 tSNE. In 19th IEEE Eurographics Conference on Visualization (EuroVis).
 Okoe, M., Jianu, R., & Kobourov, S. G. (2017, September). Revisited Experimental Comparison of NodeLink and Matrix Representations. In Graph Drawing and Network Visualization  25th International Symposium, GD 2017, Boston, MA, USA, September 2527, 2017, Revised Selected Papers.More infoThis 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 2527, 2017, Revised Selected Papers.More infoThis 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 GraphTheoretic Concepts in Computer Science (WG), 237251.More infoThis 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), 236248.More infoThis 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 Straightline Drawings. In 11th International Conference and Workshops on Algorithms and Computation (WALCOM), 135148.
 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 1115, 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 NodeLink and NodeLinkGroup 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 57, 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 57, 2015. Proceedings.
 Bekos, M. A., Kaufmann, M., Kobourov, S., & Veeramoni, S. (2015, January). The Maximum kDifferential 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 2426, 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, 558560.
 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). Mapbased Visualizations Increase LongTerm 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, 144155.
 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 2426, 2014, Revised Selected Papers, 125136.
 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 2629, 2014, Proceedings, 5264.
 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 79, 2014, 2732.
 Alam, M. J., Kobourov, S. G., Pupyrev, S., & Toeniskoetter, J. (2014). Happy Edges: ThresholdColoring of Regular Lattices. In Fun with Algorithms  7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 13, 2014. Proceedings, 2839.
 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, 514525.
 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, 247258.
 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 810, 2014. Proceedings, 8799.
 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, 223234.
 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 2426, 2014, Revised Selected Papers, 452463.
 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, 8087.
 Fried, D., & Kobourov, S. G. (2014). Maps of Computer Science. In IEEE Pacific Visualization Symposium, PacificVis 2014, Yokohama, Japan, March 47, 2014, 113120.
 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 2730, 2014, 778783.
 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 2426, 2014, Revised Selected Papers, 234245.
 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, 201208.More infoInformation visualization is essential in making sense out of large data sets. Often, highdimensional data are visualized as a collection of points in 2dimensional 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 geographiclike 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, 6975.More infoMinimum level nonplanar (MLNP) patterns play the role for level planar graphs that the forbidden Kuratowksi subdivisions K5 and K3,K3 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 kd trees and octrees. In PROCEEDINGS OF THE TENTH ANNUAL ACMSIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 300309.More infoGiven 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 kd trees, quadtrees, octrees, fairsplit 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 threedimensional worlds.
 Fowler, J. J., Kobourov, S. G., Hong, S., Nishizeki, T., & Quan, W. (2004). Characterization of unlabeled level planar graphs. In GRAPH DRAWING, 4875, 3749.More infoWe 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, 133151.More infoPeople 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, 254263.More infoWe 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 2colored tree together with any number of 2colored paths and (2) a 2colored outerplanar graph together with any number of 2colored 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 6colored cycles, (2) four 6colored paths, and (3) three 9colored paths.
 Duncan, C., Kobourov, S., Kumar, V., , ., , ., & , . (2001). Optimal constrained graph exploration. In PROCEEDINGS OF THE TWELFTH ANNUAL ACMSIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 807814.More infoWe 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 nonadjacent 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].
 EstrellaBalderrama, A., Fowler, J. J., Kobourov, S. G., Kaufmann, M., & Wagner, D. (2001). Characterization of unlabeled level planar fees. In Graph Drawing, 4372, 367379.More infoConsider 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 nlevel graph and is said to be nlevel planar if it can be drawn with straightline edges and no crossings while keeping each vertex on its own level. In this paper, we consider the class of trees that are nlevel planar regardless of their labeling. We call such trees unlabeled level planar (ULP). Our contributions are threefold. 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/9783642278488_6501