Publications

The author order is alphabetical for most of my publications.
See also Google Scholar and DBLP.

Journal Articles

• Short and Simple Cycle Separators in Planar Graphs

  Eli Fox-Epstein, Shay Mozes, Phitchaya Mangpo Phothilimthana, and Christian Sommer
  ACM Journal of Experimental Algorithmics, Special Issue for the 14th Meeting on Algorithm Engineering and Experiments (ALENEX), Volume 21, Issue 2 (pp. 2:1-24), 2016

• Shortest-Path Queries in Static Networks

  Christian Sommer
  ACM Computing Surveys, Volume 46, Issue 4 (pp. 45:1-31), 2014

• A Compact Routing Scheme and Approximate Distance Oracle for Power-Law Graphs

  Wei Chen, Christian Sommer, Shang-Hua Teng, and Yajun Wang
  ACM Transactions on Algorithms, Volume 9, Issue 1 (pp. 4:1-26), 2012

• Approximate Shortest Path Queries Using Voronoi Duals

  Shinichi Honiden, Michael E. Houle, Christian Sommer, and Martin Wolff
  Transactions on Computational Science, Volume IX, Special Issue for the 6th International Symposium on Voronoi Diagrams in Science and Engineering, LNCS 6290 (pp. 28-53), 2010

• On Shortest Disjoint Paths in Planar Graphs

  Yusuke Kobayashi and Christian Sommer
  Discrete Optimization, Volume 7, Issue 4 (pp. 234-245), 2010

• A Note on Coloring Sparse Random Graphs

  Christian Sommer
  Discrete Mathematics, Volume 50, Issue 10 (pp. 3381-3384), 2009

Papers in Refereed Conference Proceedings

List restricted to papers with algorithmic content. Work already published in journals is listed above only.

• Fast Map Matching with Vertex-Monotone Frechet Distance

  Daniel Chen, Christian Sommer, and Daniel Wolleb
  ATMOS 2021 - 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (pp. 10:1--10:20)

• Traffic-Aware Routing in Road Networks

  Daniel Delling, Dennis Schieferdecker, and Christian Sommer
  ICDE 2018 - 34th IEEE International Conference on Data Engineering (pp. 1543-1548)

• All-Pairs Approximate Shortest Paths and Distance Oracle Preprocessing

  Christian Sommer
  ICALP 2016 - 43rd International Colloquium on Automata, Languages and Programming, Track A: Algorithms, Complexity and Games (pp. 55:1-13)

• On Balanced Separators in Road Networks

  Aaron Schild and Christian Sommer
  SEA 2015 - 14th International Symposium on Experimental Algorithms (pp. 286-297)

• Structured Recursive Separator Decompositions for Planar Graphs in Linear Time

  Philip N. Klein, Shay Mozes, and Christian Sommer
  STOC 2013 - 45th ACM Symposium on Theory of Computing (pp. 505-514)

• More Compact Oracles for Approximate Distances in Undirected Planar Graphs

  Ken-ichi Kawarabayashi, Christian Sommer, and Mikkel Thorup
  SODA 2013 - 24th ACM-SIAM Symposium on Discrete Algorithms (pp. 550-563)

• Exact Distance Oracles for Planar Graphs

  Shay Mozes and Christian Sommer
  SODA 2012 - 23rd ACM-SIAM Symposium on Discrete Algorithms (pp. 209-222)

• Shortest-Path Queries for Complex Networks: Exploiting Low Tree-width Outside the Core

  Takuya Akiba, Christian Sommer, and Ken-ichi Kawarabayashi
  EDBT 2012 - 15th International Conference on Extending Database Technology (pp. 144-155)

• Practical Route Planning Under Delay Uncertainty: Stochastic Shortest Path Queries

  Sejoon Lim, Christian Sommer, Evdokia Nikolova, and Daniela Rus
  RSS 2012 - Robotics: Science and Systems VIII (pp. 249-256)

• Approximating Shortest Paths in Spatial Social Networks

  Carlo Ratti and Christian Sommer
  SocialCom 2012 - 4th ASE/IEEE International Conference on Social Computing (pp. 585-586)

• Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs

  Ken-ichi Kawarabayashi, Philip N. Klein, and Christian Sommer
  ICALP 2011 - 38th International Colloquium on Automata, Languages and Programming, Track A: Algorithms, Complexity and Games (pp. 135-146)

• Sparse Spanners vs. Compact Routing

  Cyril Gavoille and Christian Sommer
  SPAA 2011 - 23rd ACM Symposium on Parallelism in Algorithms and Architectures (pp. 225-234)

• Approximate Distance Queries for Weighted Polyhedral Surfaces

  Hristo N. Djidjev and Christian Sommer
  ESA 2011 - 19th European Symposium on Algorithms (pp. 579-590)

• Data-Driven Trajectory Smoothing

  Frédéric Chazal, Daniel Chen, Leonidas J. Guibas, Xiaoye Jiang, and Christian Sommer
  GIS 2011 - 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (pp. 251-260)

• Distance Oracles for Sparse Graphs

  Christian Sommer, Elad Verbin, and Wei Yu
  FOCS 2009 - 50th IEEE Symposium on Foundations of Computer Science (pp. 703-712)

• Distributed Arrays: A P2P Data Structure for Efficient Logical Arrays

  Daisuke Fukuchi, Christian Sommer, Yuichi Sei, and Shinichi Honiden
  INFOCOM 2009 - 28th IEEE International Conference on Computer Communications (pp. 1458-1466)

• Balancing Graph Voronoi Diagrams

  Shinichi Honiden, Michael E. Houle, and Christian Sommer
  ISVD 2009 - 6th International Symposium on Voronoi Diagrams in Science and Engineering (pp. 183-191)

Theses

• Approximate Shortest Path and Distance Queries in Networks

  Christian Sommer
  PhD thesis, University of Tokyo, 2010

• Robust Combiners for Cryptographic Primitives

  Christian Sommer
  Master's thesis, ETH Zurich, 2006