Skip to main content
eScholarship
Open Access Publications from the University of California

Scholarly Works (3 results)

  • Thesis
  • Peer Reviewed
UC Irvine Electronic Theses and Dissertations (2018)

We study some geographic and geometric graphs namely road networks and clustered graphs from topological viewpoint, i.e., we consider them as embedded graphs, graphs in which the ordering of edges (clockwise or anti-clockwise) incident on each vertex is uniquely defined. A road network is a graph with a vertex at each intersection of roads and an edge for each segment of road between the intersections. A clustered graph is a graph whose vertices belong to properly nested clusters. We present algorithms and models for some problems related to road networks and clustered graphs.

The first problem we consider is how a road network has evolved over time, given two snapshots from different dates. These graph can also have geometric/geographic information, such as the GPS coordinates of some vertices or labels identifying road names. As there can be vertices and edges without such geometric/geographic information, we take a strictly topological approach for the problem. We propose an algorithm, which runs in polynomial time for non degenerate-road networks, and outputs portions of the network that remained intact and also points out added or removed portions. We also analyze our algorithm experimentally taking US road network data from the TIGER/Line archive of the U.S. Census Bureau as input data set and show that our algorithm produces good results in practice.

In the second problem, we study the non-planar properties of road networks. We normally consider road networks as planar graph but they are actually non-planar due to non-intersecting crossings caused by overpass, underpass, or tunnel. We provide a mathematical model of nearly-planar graphs and show that the non-planar graphs that fit this model do have polynomial expansion, i.e., they and all their subgraphs have small separators. We also analyze the Urban Road Network Data set and show that the model is indeed a good fit for non-planar road networks.

Finally, we investigate the C-Planarity problem which asks for drawing of a clustered graph in which each cluster is represented by a simple closed region with no edge-edge crossings, no region-region crossings, and no unnecessary edge-region crossings. We study C-Planarity for embedded flat clustered graphs, embedded graphs whose clusters partition the vertex set. We provide a subexponential-time algorithm to test C-Planarity for these graphs when the face size is bounded. Further, we also study a variation of tree decomposition in which, for each face, including the outer face, there is a bag that contains every vertex of the face. We show that C-Planarity is fixed-parameter tractable with the embedded-width of the underlying graph and the number of disconnected clusters as parameters.

    Cover page: Topological Algorithms for Geographic and Geometric GraphsCreative Commons 'BY' version 4.0 license
    • Article
    • Peer Reviewed
    LBL Publications (2016)
    Well-established fine-scale urban mobility models today depend on detailed but cumbersome and expensive travel surveys for their calibration. Not much is known, however, about the set of mechanisms needed to generate complete mobility profiles if only using passive datasets with mostly sparse traces of individuals. In this study, we present a mechanistic modeling framework (TimeGeo) that effectively generates urban mobility patterns with resolution of 10 min and hundreds of meters. It ties together the inference of home and work activity locations from data, with the modeling of flexible activities (e.g., other) in space and time. The temporal choices are captured by only three features: the weekly home-based tour number, the dwell rate, and the burst rate. These combined generate for each individual: (i) stay duration of activities, (ii) number of visited locations per day, and (iii) daily mobility networks. These parameters capture how an individual deviates from the circadian rhythm of the population, and generate the wide spectrum of empirically observed mobility behaviors. The spatial choices of visited locations are modeled by a rank-based exploration and preferential return (r-EPR) mechanism that incorporates space in the EPR model. Finally, we show that a hierarchical multiplicative cascade method can measure the interaction between land use and generation of trips. In this way, urban structure is directly related to the observed distance of travels. This framework allows us to fully embrace the massive amount of individual data generated by information and communication technologies (ICTs) worldwide to comprehensively model urban mobility without travel surveys.
      Cover page: The TimeGeo modeling framework for urban motility without travel surveys.
      • Article
      • Peer Reviewed
      LBL Publications (2019)
      Accurate occupancy is crucial for planning for sustainable buildings. Using massive, passively-collected mobile phone data, we introduce a novel framework to estimate building occupancy at unprecedented scale. We show that, at urban-scale, occupancy differs widely from current estimates based on building types. For commercial buildings, we find typical occupancy rates are 5 times lower than current assumptions imply, while for residential buildings occupancy rates vary widely by neighborhood. Our mobile phone based occupancy estimates are integrated with a state-of-the-art urban building energy model to understand their impact on energy use predictions. Depending on the assumed relationship between occupancy and internal building loads, we find energy consumption which differs by +1% to -15% for residential buildings and by -4% to -21% for commercial buildings, compared to standard methods. This highlights a need for new occupancy-to-load models which can be applied at urban-scale to the diverse set of city building types.
        Cover page: Planning for sustainable cities by estimating building occupancy with mobile phones.
        Top