Publications
Java Demos
Rectangular Cartograms

 

A more recent (and usually more complete) version of the paper is available.
An older version of the paper is available.
  In both cases, just follow the link to an electronic copy.

 

  • Kinetic Data Structures
    B. Speckmann.
    Encyclopedia of Algorithms, M.-Y. Kao (editor), Springer Verlag, pp. 417-419, 2008.

  • Computational Geometry: Fundamental Structures
    M. de Berg and B. Speckmann.
    D.P. Mehta and S. Sahni (eds.), Handbook of Data Structures and Applications, CRC Press, pp. 62.1–62.20, 2005.
 
 

  • Geometric Simultaneous Embeddings of a Graph and a Matching
    S. Cabello, M. van Kreveld, G. Liotta, H. Meijer, B. Speckmann, and K. Verbeek.
    Proc. 17th International Symposium on Graph Drawing (GD 09), 2009 (to appear).

  • On Planar Supports for Hypergraphs
    K. Buchin, M. van Kreveld, H. Meijer, B. Speckmann, and K. Verbeek.
    Proc. 17th International Symposium on Graph Drawing (GD 09), 2009 (to appear).

  • Flip Graphs of Bounded-Degree Triangulations
    O. Aichholzer, T. Hackl, D. Orden, P. Ramos, G. Rote, A. Schulz, and B. Speckmann.
    Proc. European Conference on Combinatorics, Graph Theory and Applications (EuroComb), pp. 509–513, Electronic Notes in Discrete Mathematics 34, 2009.

  • Connect the Dot: Computing Feed-links with Minimum Dilation
    B. Aronov, K. Buchin, M. Buchin, M. van Kreveld, M. Löffler, J. Luo, R. I. Silveira, and B. Speckmann.
    Proc. 11th Algorithms and Data Structures Symposium (WADS), pp. 49–60, Lecture Notes in Computer Science 5664, 2009.

  • Plane Graphs with Parity Constraints
    O. Aichholzer, T. Hackl, M. Hoffmann, A. Pilz, G. Rote, B. Speckmann, and Birgit Vogtenhuber.
    Proc. 11th Algorithms and Data Structures Symposium (WADS), pp. 13 –24, Lecture Notes in Computer Science 5664, 2009.

  • Area-Universal Rectangular Layouts
    D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek.
    Proc. 25th ACM Symposium on Computational Geometry (SoCG), pp. 267–276, 2009.

  • Shooting permanent rays among disjoint polygons in the plane
    M. Ishaque, B. Speckmann, and C.D. Tóth.
    Proc. 25th ACM Symposium on Computational Geometry (SoCG), pp. 51–60, 2009.

  • Detecting Hotspots in Geographic Networks
    K. Buchin, S. Cabello, J. Gudmundsson, M. Löffler, J. Luo, G. Rote, R. I. Silveira, B. Speckmann, and T. Wolle.
    Advances in GIScience, Proc. 12th AGILE International Conference on Geographic Information Science (AGILE), pp. 217–231, Lecture Notes in Geoinformation and Cartography, 2009.
    (Best Paper Award)

  • Subdivision Drawings of Hypergraphs
    M. Kaufmann, M. van Kreveld, and B. Speckmann.
    Proc. 16th International Symposium on Graph Drawing (GD 08), pp. 396–407, Lecture Notes in Computer Science 5417, 2009.

  • Feed-links for Network Extensions
    B. Aronov,  K. Buchin,  M. Buchin,  B. Jansen,  T. de Jong,  M. van Kreveld, M. Löffler,  J. Luo,  R. I. Silveira, and B. Speckmann.
    Proc. 16th International Conference on Advances in Geographic Information Systems (ACM GIS), pp. 308–316, 2008.

  • Polychromatic Colorings of Plane Graphs
    N. Alon, R. Berke, M. Buchin, K. Buchin, P. Csorba, S. Shannigrahi, B. Speckmann, and P. Zumstein.
    Proc. 24th ACM Symposium on Computational Geometry (SoCG), pp. 338–345, 2008.

  • Matched Drawings of Planar Graphs
    E. Di Giacomo, W. Didimo, M. van Kreveld, G. Liotta, and B. Speckmann.
    Proc. 15th International Symposium on Graph Drawing (GD 07), pp. 183–194, Lecture Notes in Computer Science 4875, 2008.

  • Edges and Switches, Tunnels and Bridges
    D. Eppstein, M. van Kreveld, E. Mumford, and B. Speckmann.
    Proc. 10th Workshop on Algorithms and Data Structures (WADS), pp. 77–88, Lecture Notes in Computer Science 4619, 2007.

  • Maximizing Maximal Angles for Plane Straight Line Graphs
    O. Aichholzer, T. Hackl, M. Hoffmann, C. Huemer, A. Por, F. Santos, B. Speckmann, and B. Vogtenhuber.
    Proc. 10th Workshop on Algorithms and Data Structures (WADS), pp. 458–469, Lecture Notes in Computer Science 4619, 2007.

  • Kinetic kd-Trees and Longest-Side kd-Trees
    M.A. Abam, M. de Berg, and B. Speckmann.
    Proc. 23rd ACM Symposium on Computational Geometry (SoCG), pp. 364–372, 2007.

  • Optimal BSPs and Rectilinear Cartograms
    M. de Berg, E. Mumford, and B. Speckmann.
    Proc. 14th International Symposium on Advances in Geographic Information Systems (ACM GIS), pp. 19–26, 2006.

  • Kinetic Collision Detection for Convex Fat Objects
    M.A. Abam, M. de Berg, S.-H. Poon, and B. Speckmann.
    Proc. 14th European Symposium on Algorithms (ESA), pp. 4–15, Lecture Notes in Computer Science 4168, 2006.

  • Algorithmic Aspects of Proportional Symbol Maps
    S. Cabello, H. Haverkort, M. van Kreveld, and B. Speckmann.
    Proc. 14th European Symposium on Algorithms (ESA), pp. 720–731, Lecture Notes in Computer Science 4168, 2006.

  • Decompositions, Partitions, and Coverings with Convex Polygons and Pseudo-Triangles
    O. Aichholzer, C. Huemer, S. Renkl, B. Speckmann, and C.D. Tóth.
    Proc. 31st International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 86–97, Lecture Notes in Computer Science 4162, 2006.

  • A Linear Programming Approach to Rectangular Cartograms
    B. Speckmann, M. van Kreveld, and S. Florisson.
    Progress in Spatial Data Handling, Proc. 12th International Symposium on Spatial Data Handling (SDH), pp. 527–546, 2006.

    Webpage Rectangular Cartograms

  • On Rectilinear Duals for Vertex-Weighted Plane Graphs
    M. de Berg, E. Mumford, and B. Speckmann.
    Proc. 13th International Symposium on Graph Drawing (GD 05), pp. 61–72, Lecture Notes in Computer Science 3843, 2006.

  • Rectangular Cartogram Computation with Sea Regions
    M. van Kreveld and B. Speckmann.
    Proc. 22nd International Cartographic Conference (ICC), 2005.

  • Off-line Admission Control for Advance Reservations in Star Networks
    U. Adamy, T. Erlebach, D. Mitsche, I. Schurr, B. Speckmann, and E. Welzl.
    Proc. 2nd Workshop on Approximation and Online Algorithms (WAOA), pp. 211–224, Lecture Notes in Computer Science 3351, 2005.

  • Efficient Detection of Motion Patterns in Spatio-Temporal Data Sets
    J. Gudmundsson, M. van Kreveld, and B. Speckmann.
    Proc. 12th International Symposium on Advances in Geographic Information Systems (ACM GIS), pp. 250–257, 2004.

  • On Rectangular Cartograms
    M. van Kreveld and B. Speckmann.
    Proc. 12th European Symposium on Algorithms (ESA), pp. 724–735, Lecture Notes in Computer Science 3221, 2004.

    Java Demo Rectangular Cartograms   Webpage Rectangular Cartograms

  • Bounds on the k-Neighborhood for Locally Uniform Sampled Surfaces
    M. Andersson, J. Giesen, M. Pauly, and B. Speckmann.
    Proc. 1st Symposium on Point-Based Graphics, pp. 167–171 plus color page 233, 2004.

  • Pointed Binary Encompassing Trees
    M. Hoffmann, B. Speckmann, and C.D. Tóth.
    Proc. 9th Scandinavian Workshop on Algorithm Theory (SWAT), pp. 442–454, Lecture Notes in Computer Science 3111, 2004.

  • The Zigzag Path of a Pseudo-Triangulation
    O. Aichholzer, G. Rote, B. Speckmann, and I. Streinu
    Proc. 8th Workshop on Algorithms and Data Structures (WADS), pp. 377–388, Lecture Notes in Computer Science 2748, 2003.

  • Allocating Vertex pi-guards in Simple Polygons via Pseudo-Triangulations
    B. Speckmann and C.D. Tóth.
    Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 109–118, 2003.

  • Cutting a Country for Smallest Square Fit
    M. van Kreveld and B. Speckmann.
    Proc. 13th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science 2518, pp. 91–102, 2002.

  • Kinetic Maintenance of Context-Sensitive Hierarchical Representations for Disjoint Simple Polygons
    D. Kirkpatrick and B. Speckmann.
    Proc. 18th ACM Symposium on Computational Geometry (SoCG), pp. 179–188, 2002.

  • Separation Sensitive Kinetic Separation Structures for Convex Polygons
    D. Kirkpatrick and B. Speckmann.
    Proc. Japan Conference on Discrete and Computational Geometry (JCDCG), Lecture Notes in Computer Science 2098, pp. 222–236, 2001.

  • Kinetic Collision Detection for Simple Polygons
    D. Kirkpatrick, J. Snoeyink, and B. Speckmann.
    Proc. 16th ACM Symposium on Computational Geometry (SoCG), pp. 322–330, 2000.

    Java Demo Kinetic collision detection for simple polygons

  • Efficient Algorithms for Maximum Regression Depth
    M. van Kreveld, J.S.B. Mitchell, P. Rousseeuw, M. Sharir, J. Snoeyink, and B. Speckmann.
    Proc. 15th ACM Symposium on Computational Geometry (SoCG), pp. 31–40, 1999.

    Java Demo Computing maximum regression depth
 
 

  • Homotopic Rectilinear Routing with Few Links and Thick Edges
    B. Speckmann and K. Verbeek.
    Abstr. 25th European Workshop on Computational Geometry (EuroCG), Brussels, Belgium, pp. 243–246, 2009.

  • Area-Universal Rectangular Layouts
    D. Eppstein, E. Mumford, B. Speckmann, and K. Verbeek.
    Abstr. 25th European Workshop on Computational Geometry (EuroCG), Brussels, Belgium, pp. 247–250, 2009.

  • Triangulating and Guarding Realistic Polygons
    G. Aloupis, P. Bose, V. Dujmovic, C. Gray, S. Langerman, and B. Speckmann.
    Proc. 20th Canadian Conference on Computational Geometry (CCCG), pp. 107–111, 2008.

  • Colour Patterns for Polychromatic Four-colourings of Rectangular Subdivisions
    H. Haverkort, M. Löffler, E. Mumford, M. O'Meara, J. Snoeyink, and B. Speckmann.
    Abstr. 24th European Workshop on Computational Geometry (EuroCG), pp. 75–78, Nancy, France, 2008.

  • On the Number of Empty Pseudo-Triangles in Point Sets
    M. van Kreveld and B. Speckmann.
    Proc. 19th Canadian Conference on Computational Geometry (CCCG), pp. 37–40, 2007.

  • On (Pointed) Minimum Weight Pseudo-Triangulations
    O. Aichholzer, F. Aurenhammer, T. Hackl, and B. Speckmann.
    Proc. 19th Canadian Conference on Computational Geometry (CCCG), pp. 209–212, 2007.

  • Maximizing Maximal Angles for Plane Straight Line Graphs
    O. Aichholzer, T. Hackl, M. Hoffmann, C. Huemer, F. Santos, B. Speckmann, and B. Vogtenhuber.
    Abstr. 23rd European Workshop on Computational Geometry (EuroCG), pp. 98–101, Graz, Austria, 2007.

  • Kinetic kd-Trees
    M.A. Abam, M. de Berg, and B. Speckmann.
    Abstr. 23rd European Workshop on Computational Geometry (EuroCG), pp. 126–129, Graz, Austria, 2007.

  • Edges and Switches, Tunnels and Bridges
    D. Eppstein, M. van Kreveld, E. Mumford, and B. Speckmann.
    Abstr. 23rd European Workshop on Computational Geometry (EuroCG), pp. 146–149, Graz, Austria, 2007.

  • Kinetic Collision Detection for Balls Rolling on a Plane
    M.A. Abam, M. de Berg, S.-H. Poon, and B. Speckmann.
    Abstr. 22nd European Workshop on Computational Geometry (EuroCG), pp. 55–58, Delphi, Greece, 2006.

  • On Pseudo-Convex Decompositions, Partitions, and Coverings
    O. Aichholzer, C. Huemer, S. Renkl, B. Speckmann, C.D. Tóth.
    Abstr. 21st European Workshop on Computational Geometry (EuroCG), pp. 89–92, Eindhoven, The Netherlands, 2005.

  • Area-Preserving Approximations of Polygonal Paths
    P. Bose, S. Cabello, O. Cheong, J. Gudmundsson, M. van Kreveld, and B. Speckmann.
    Accepted for presentation at Japan Conference on Discrete and Computational Geometry (JCDCG), 2004.

  • On Rectangular Cartograms
    M. van Kreveld and B. Speckmann.
    Proc. 10th Annual Conference of the Advanced School for Computing and Imaging (ASCI), pp. 11–16, Ouddorp, The Netherlands, 2004.

  • On Rectangular Cartograms
    M. van Kreveld and B. Speckmann.
    Abstr. 20th European Workshop on Computational Geometry (EuroCG), pp. 69–72, Sevilla, Spain, 2004.

  • On the Number of Pseudo-Triangulations of Certain Point Sets
    O. Aichholzer, D. Orden, F. Santos, and B. Speckmann.
    Abstr. 20th European Workshop on Computational Geometry (EuroCG), pp. 119–122, Sevilla, Spain, 2004.

  • Pointed Binary Encompassing Trees
    M. Hoffmann, B. Speckmann, and C.D. Tóth.
    Abstr. 20th European Workshop on Computational Geometry (EuroCG), pp. 131–134, Sevilla, Spain, 2004.

  • Degree Bounds for Constrained Pseudo-Triangulations
    O. Aichholzer, M. Hoffmann, B. Speckmann, and C.D. Tóth.
    Proc. 15th Canadian Conference on Computational Geometry (CCCG), pp. 155–158, 2003.

  • On the Number of Pseudo-Triangulations of Certain Point Sets
    O. Aichholzer, D. Orden, F. Santos, and B. Speckmann.
    Proc. 15th Canadian Conference on Computational Geometry (CCCG), pp. 141–144, 2003.

  • The Path of a Pseudo-Triangulation
    O. Aichholzer, B. Speckmann, and I. Streinu.
    Abstr. DIMACS Workshop on Computational Geometry, Piscataway (NJ), USA, 2002.

  • Convexity Minimizes Pseudo-Triangulations
    O. Aichholzer, F. Aurenhammer, H. Krasser, and B. Speckmann.
    Proc. 14th Canadian Conference on Computational Geometry (CCCG), pp. 158–161, 2002.

  • Vertex pi-guards in Simple Polygons
    B. Speckmann and C.D. Tóth.
    Abstr. 18th European Workshop on Computational Geometry, pp. 12–15, Warsaw, Poland, 2002.

  • Tight Degree Bounds for Pseudo-triangulations of Points
    L. Kettner, D. Kirkpatrick, and B. Speckmann.
    Proc. 13th Canadian Conference on Computational Geometry (CCCG), pp. 117–120, 2001.

  • Bounded-degree Pseudo-triangulations of Points
    L.  Kettner, A. Mantler, J. Snoeyink, B. Speckmann, and F. Takeuchi.
    Abstr. 17th European Workshop on Computational Geometry (EuroCG), pp. 19–22, Berlin, Germany, 2001.

  • Separation Sensitive Kinetic Collision Detection for Simple Polygons
    D. Kirkpatrick and B. Speckmann.
    Abstr. 10th Annual Fall Workshop on Computational Geometry, Stony Brook (NY), USA, 2000.
         
  • Robust Regression Estimators
    B. Speckmann.
    Proc. 9th PRECARN-IRIS Conference, poster session, Toronto (ON), Canada, 1999.

  • Tripod: a minimalist data structure for embedded triangulations
    J. Snoeyink and B. Speckmann.
    Proc. Workshop on Computational Graph Theory and Combinatorics, Victoria (BC), Canada, 1999.

  • Easy Triangle Strips for TIN Terrain Models
    B. Speckmann and J. Snoeyink.
    Proc. 9th Canadian Conference on Computational Geometry (CCCG), pp. 239–244, 1997.

  • Compact Triangulated Terrain Models
    B. Speckmann.
    Proc. 7th PRECARN-IRIS Conference, poster session, Ottawa (ON), Canada, 1997.


  • Placing Diagrams and Symbols on Maps
    M. van Kreveld and B. Speckmann.
    NVTI Niewsbrief (Newsletter of the Dutch Association for Theoretical Computer Science), 12:14–24, 2008.

  • Algorithmic Aspects of Cartogram Computation
    B. Speckmann.
    Bulletin of the European Association for Theoretical Computer Science, 92:33–43, 2007.

  • Algorithms for cartograms and other specialized maps
    B. Speckmann.
    Geo-information and computational geometry, P. van Oosterom and M. van Kreveld (eds.), Netherlands Geodetic Commission, 44:26-34, 2006.

  • Automated construction of Rectangular Cartograms
    M. van Kreveld and B. Speckmann.
    XOOTIC Magazine, 11(1):5–11, 2005.

  • Kinetic Data Structures for Collision Detection
    Bettina Speckmann.
    PhD Thesis, Department of Computer Science, University of British Columbia, 2001.

  • Verschneidung einfach zusammenhängender planarer Unterteilungen auf Basis der QCEL Datenstruktur
    Bettina Speckmann.
    Diplomarbeit (Master’s Thesis), Westfälische Wilhelms-Universität Münster, 1996.
  
last modified: 18-Nov-2009