## Abstract

The world is urbanizing quickly with nearly 4 billion people presently living in urban areas, about 1 billion of them in slums. Achieving sustainable development from rapid urbanization relies critically on creating cities without slums. We show that it is possible to diagnose systematically the central physical problem of slums—the lack of spatial accesses and related services—using a topological analysis of neighborhood maps and resolved by finding solutions to a sequence of constrained optimization problems. We set up the problem by showing that the built environment of any city can be decomposed into two types of networked spaces—accesses and places—and prove that these spaces display universal topological characteristics. We then show that while the neighborhoods of developed cities express the same common topology, urban slums fall into a different topological class. We demonstrate that it is always possible to find solutions that grow a street network in existing slums, providing universal accesses at minimal disruption and cost. We then show how elaborations of this procedure that include local preferences and reduce travel distances between places result from additional access construction. These methods are presently taking effect in neighborhoods in Cape Town (South Africa) and Mumbai (India), demonstrating their practical feasibility and emphasizing their role as a platform to enable communities and local governments to combine technical knowledge with local aspirations into contextually appropriate urban sustainable development solutions.

## INTRODUCTION

Presently, about 4 billion people worldwide live in urban areas, about 1 billion of them in slums. UN-Habitat estimates that by 2050, 6.4 billion people will live in cities and 3 billion could be living in slums if no practical framework for action is implemented to address the issue (*1*). Recent international agreements, such as the Sustainable Development Goals and the New Urban Agenda, call for the transformation of all slums into serviced, formal neighborhoods, according to a path set by the coordination of universal principles and local knowledge and priorities. There has been substantial investment in community-driven slum enumeration, upgrading, and development (*2*–*6*). Slums are typically associated with stark environmental challenges (*6*, *7*) and many types of social and economic exclusion that inhibit people and cities from fulfilling their potential for human development and economic growth (*6*, *8*). Thus, seizing the opportunity for sustainable development created by urbanization (*9*–*11*) and enabled by growing local action critically hinges on creating “cities without slums” (*1*–*4*, *10*).

Although the scale and scope of worldwide urban growth and poverty are unprecedented, the essential nature of the problem is not (*1*, *12*). Here, we focus on the subset of all slums and informal settlements for which the spatial layout of homes and businesses does not allow sufficient space for accessing and constructing formal networked urban services such as streets and sanitation networks. At the physical level, these slums are generally characterized by informal or unplanned land uses. This often leads to a lack of connections between places of work and residence to infrastructure and services (*1*, *6*, *13*). Although some access always exists in practice for personal movement (for example, see fig. S1), many places of human activity in slums lack an address and cannot be reached by a vehicle. This means that essential services, such as water and sanitation, are absent from homes and workspaces and that emergency services, such as health assistance (for example, by an ambulance) or fire protection, are nearly impossible to deliver, creating conditions that impede ordinary activities, degrade the environment, and amplify humanitarian crises (*1*, *6*–*9*).

To make sense of the character of slums in scientific terms requires placing them in the context of other urban neighborhoods. Cities exist in many different geometries, from regular grids to curvy mazes of streets and alleys. Urban form in any given place is shaped both by constraints that apply to all cities, such as the circulation of people, goods, and information, and by processes that are particular to each place, such as geography, the technological and social context as a city builds, and the history of choices made by residents and planners (*14*, *15*). This diversity of form is often aesthetically appealing (*14*) but has defied quantitative explanations or replication by known design practices. A long history of urban planning and urban geography (*14*, *16*) and, more recently, of data-driven statistical analysis (*15*, *17*) has attempted to classify urban spatial patterns with an eye toward optimal design, but the quest for ideal forms has remained elusive.

Here, we show that topology, and not geometry, dictates the essential spatial form of cities. Topology provides a general quantitative measure of families of surfaces and the means to establish the equivalence between diverse geometries when these can be continuously deformed into each other. Consequently, topological invariance allows for considerable freedom of geometric form so long as essential functional relationships are preserved. When applied to cities, this methodology allows us to describe connectivity as one essential spatial relationship between street or infrastructure networks and buildings and public places. The description of urban form from a topological perspective leads to analytical tools for identifying incipient urban development in informal neighborhoods and generating proposals for efficient ways to address associated deficits of infrastructure and services.

Taking this perspective as our starting point, we derive here the general topology of cities and show how it is intimately associated with neighborhood development (extended discussion in sections SA to SD). To do this, we divide urban built spaces into two categories (*18*): (i) access systems (that is, roads, streets, and paths) and (ii) places (buildings and public spaces). These two types of physical spaces span the entire city and are interconnected (figs. S1 to S5). Using access systems and places, we can describe each city as a connected set of blocks, each of which is an island surrounded by infrastructure that (ideally) mediates access to each place internal to it (Fig. 1). As we demonstrate below, this framework establishes that urban slums fall into distinct topological classes from developed neighborhoods because infrastructure access to places within is incipient and, in many cases, altogether missing. This access problem can be resolved mathematically by finding a physical transformation of the streets and accesses within slums that changes the neighborhood’s topology at minimal costs. This strategy provides a rigorous and comprehensive approach to the fundamental properties of urban design anywhere, while leaving choices and details of form to be decided locally in a context-sensitive manner (sections SA and SB).

The novelty of the approach proposed here is to show how tools of topology and graph theory can be applied to real maps of neighborhoods to not only diagnose but also solve critical problems of development. Providing poor, informal neighborhoods with addresses, accesses, and services has critical impacts for human health and environmental sustainability and becomes a platform for socioeconomic development. Doing so with tools that can promote dialog and a collaborative process of urban planning between communities and their governments is also essential in most cases and is known to produce better solutions at lower costs (*2*, *4*, *5*, *19*). To show how this can be done, in the next section, we present the basis for understanding the general topology of cities, which allows us to measure the exceptionality of slums via a geometric graph construction. We then show how this construction can be implemented to analyze the map of any city block and measure the lack of physical accesses. When accesses are missing, we show how new streets and paths that connect all structures in the neighborhood to the existing infrastructure network at minimal cost can be identified and proposed. We also show how these street networks can subsequently be elaborated, if desired, to minimize distances between places via the strategic placement of additional street segments. Throughout, our approach describes what is general about access problems in cities, and therefore implementable by algorithms, and what is particular and thus must be left to local decisions. We conclude with a discussion of the scalability of these methods and their potential to markedly accelerate processes of sustainable development in fast-growing cities, especially in middle- and low-income nations.

## RESULTS

We now introduce a framework for characterizing the topology of cities, first by considering the topology of urban access systems, followed by the relationship between places and accesses, and finally the relative position among places within each city block. We then demonstrate an algorithm to identify places that are disconnected from the broader urban infrastructure and show how missing infrastructure can be proposed at minimal interference and cost (see also openreblock.org). Elaborations of this procedure to provide additional connectivity that reduces travel distance are also demonstrated to provide a complete set of tools that generate known patterns of change in the physical layout of cities.

### Topology of access networks

The general topology of the access system in any city is relatively simple and has recently been analyzed in many cases in terms of the network analysis of street networks (*16*, *20*–*22*). Notwithstanding a fast-growing literature in graph analysis of these spatial networks, a number of simple but fundamental results for the topology of all cities have never—to the best of our knowledge—been explicitly articulated. Here, we provide the general arguments for these results; mathematical proofs are based on well-known theorems of topology and graph theory and are given explicitly in section SA.

The physical volume of all paths, streets, and roads in a city is a connected two-dimensional surface: Any point on this surface can be reached from any other point on the same surface. This surface ends where buildings begin and at external city boundaries. Thus, the urban access network surface, *U*, of any city has a number of internal boundaries, *b*, one for each city block and another for city limits. Mathematically, such an access system is topologically equivalent to a disk with *b* punctures or “holes” (or a sphere with *b +* 1 disks removed). In this way, all urban access systems with the same number *b* of city blocks (i) are topologically equivalent and (ii) share an invariant number, the Euler characteristic χ(*U*) *=* 1 *− b*, which is independent of geometry. From this perspective, the Euler characteristic χ(*U*) of a city provides a universal spatial measure of its size and a way to relate the topology of any city to that of any other. In particular, this result also states (iii) that sections of cities with the same number of blocks are topologically equivalent and, thus, can be deformed into each other, a property we illustrate in movie S1, showing how central sections of Mumbai can be deformed into suburban subdivisions of Las Vegas, NV, and, in turn, into regular gridded city blocks of a dense city like Manhattan, NY. This perspective on the “shape of cities” allows us to readily understand why cities can exist in so many different forms, from simple regular grids to more organic plans. Topology allows us to see that these forms are functionally equivalent, as long as they refer to the same number of city blocks.

### Topology of places

The topology of places depends on how they are spatially organized relative to the access network as well as to each other. We will show that the first of these is sufficient to understand most planned city blocks, whereas the second will be required to understand land uses in informal settlements.

To see this, consider the examples of city blocks in Fig. 1 from cities on three different continents. Figure 1A shows a schematic city block and a graph construction used to identify internal places not connected to the surrounding street network. As particular cases, the distinctive feature of Fig. 1 (B and C), showing typical city blocks in New York City in 2014 and Prague circa 1840, is that, despite very different geometries, all places are immediately adjacent to streets. This should be expected in general, as each place of residence or work has a door or driveway that connects its interior to its adjacent city’s streets and from there to every other place. Thus, the adjacency of each place to a section of the street network should be expected to be a general property of urban spaces. When each place within a block is adjacent to the access system, we call the corresponding city block universally accessible (section SB), meaning that all places within it can be reached in this way.

To formalize this result, we prove in section SC that the space of universally accessible places is isomorphic to its access network (fig. S4). Intuitively, this result follows from the fact that each accessible place has a path, street, or part of a street uniquely dedicated to itself. This result defines the general topology of cities, provided all their places are accessible. Then, the Euler characteristic, discussed above, gives a topological (geometry-independent) quantitative measure of city size and expresses a general type of self-similarity between urban spaces, where sections of one city can be mapped to entire towns, provided they share the same number of blocks. These results—described in detail in the Supplementary Materials—establish the universal character of urban built spaces and show how they can be transformed without loss of function by spatial deformations that preserve topology.

However, in many urban areas, city blocks and their places are not always accessible in the sense just described. These exceptions prove telling as they are typical of fast-growing urban areas with incipient infrastructure, such as slums and other poor or marginal areas.

To analyze this issue, we define a metric, *k*_{max}, called block complexity to measure the connectedness of a city block. As the name suggests, the higher the complexity value, the more difficult it is to reach places within the block starting with the existing street network. There are two equivalent ways of computing a block’s complexity. Both require that we represent the space of places in each city block by its own graph, *S*_{0}, where edges correspond to the boundaries of each parcel and nodes to their intersection (see Fig. 1A). In these graphs, each interior face in *S*_{0} represents one place as a distinct land parcel. We then create the graph *S** that is dual to *S*_{0} by replacing faces of *S*_{0} with nodes, including one node for the exterior face, and inserting edges in *S** representing adjacency of faces of *S*_{0}. Then, we define the block complexity *k*_{max} by measuring the maximum path length between the node of *S** representing the external face of *S*_{0} and any other node in *S**.

Equivalently, we can find *k*_{max} by iterating the construction of weak dual graphs to *S*_{0}; the weak dual of *S*_{0} is a graph *S*_{1}, where each parcel becomes a node and adjacency becomes an edge, but does not introduce a node for the external face of *S*_{0} (see Fig. 1). The weak dual process continues inductively to create a sequence of weak duals: *S*_{k−1}*→S*_{k}. The complexity value *k*_{max} is obtained when the sequence terminates (section SC). Figure 1A shows a simple schematic example of these nested dual graphs. Figure 1 (B to D) shows three examples from different cities.

We proceed here using the weak dual iteration approach; the key advantage of this procedure is that it is computationally faster because it does not rely on finding a shortest path for each node of *S**. Successive weak duals visually display layers of inaccessibility of places, as seen in Fig. 1, equivalent to plotting the minimum path length for each node of *S*^{*} to the external face of *S*_{0}. We prove in section SE that the block topology is simple when the second weak dual, *S*_{2}, is a tree graph and that this is a necessary and sufficient condition for city blocks to be universally accessible. In this way, the number *k*_{max} provides a quantitative measure of the difficulty of access and thus the complexity of the access problem.

To illustrate these results, Fig. 1D shows a small block from an informal settlement in Harare, Zimbabwe (see also figs. S5 to S7), which has *k*_{max} = 3. Figure 2 shows a much larger and more complex city block in Cape Town, South Africa, with *k*_{max} = 9. These examples also show that the block complexity, *k*_{max}, has an additional quantitative interpretation: The quantity (*k*_{max} − 1)/2 is the minimum number of internal boundaries that need to be crossed, starting from the most internal place in the block, to reach the external street network (see also section SE). The presence of many parcels internal to city blocks is characteristic of many of the world’s urban slums (Fig. 2 and figs. S5 to S8) (*13*).

### Slum upgrading via constrained optimization

We now turn to the central issue of this paper: how to create explicit practical solutions for urban development using neighborhood maps of places and existing accesses. The principal issue to do with neighborhood development is how to most effectively create the greatest positive change. Partly due to the efforts of grass root organizations, slum upgrading in situ has become the main strategy, preferable to evictions and relocations that too often fail to provide sustainable solutions (*2*, *5*, *13*, *19*). This practice is known as reblocking. Technically, reblocking changes the topology of a neighborhood regardless of its specific geometry by providing street and infrastructure access to each place and creating public spaces. Reblocking is an operation often identified and implemented by informal settlement communities on their own or in partnership with local governments (*1*–*5*, *13*, *23*) as the critical first step for open-ended neighborhood development (sections SC and SD).

Reblocking, by providing access to each parcel and building in a neighborhood, is the main physical enabler of any slum-upgrading strategy (*13*). This is mainly because it facilitates the introduction of urban services and infrastructure and a gradual process of morphological neighborhood change that eventually may lead to the fusion of small parcels and building upgrades and reconstruction. UN-Habitat currently recommends street-focused infrastructure upgrading as a major strategy for neighborhood development that can significantly improve socioeconomic outcomes (*13*). The costs of providing services before and after reblocking vary tremendously, often by a factor of 10 or more, making it the critical difference between providing a service or not (*24*, *25*). This is because piped urban services such as water, sanitation, and gas are much easier to design, build, and maintain when their access route follows and is buried under streets and paths.

Despite all these advantages, the reblocking process is often contentious and slow because many different access configurations are possible, and solutions require creating a public good by coordinating numerous stakeholders with different cost/benefit tradeoffs (*2*–*5*). Thus, the real world process of collectively considering many plausible alternatives tends to considerably delay practical solutions, if not precluding them altogether, especially in cases where local community groups have not been effectively engaged.

For these reasons, creating rigorous and easy-to-use planning tools that quickly analyze the problem of access and reveal good solutions and clear, quantified tradeoffs is paramount. To tackle this issue, the results above immediately suggest how to algorithmically construct “optimal reblocking” by solving a constrained optimization problem that takes a city block made of streets and parcels and proposes the addition of a minimal set of additional accesses Δ*U* that render the block universally accessible. Mathematically, we can write an algorithm that (i) computes *k*_{max} for a chosen city block; (ii) if *k*_{max} > 2, introduces a new set of accesses Δ*U* until *k*_{max} ≤ 2; and (iii) minimizes *L*(*U*), keeping *k*_{max} ≤ 2, where *L*(*U*) is the total length of accesses in *U*. In practice, the introduction of any access segments always reduces (or leaves unchanged) the block complexity, so that this quantity can be successively minimized until it becomes *k*_{max} = 2, while a minimal set of accesses is identified. Because these quantities are positive, the problem is always well posed (bounded from below).

The constraint of minimizing *L*(*U*) while guaranteeing universal connectivity also implements minimal disruption and construction costs (see Fig. 3). There is in general only one access solution that achieves the desired topological transformation (section SC). The existence of this solution proves that it is always possible to reblock a neighborhood.

Two examples of optimal reblocking configurations, obtained under absolute new construction length minimization, are shown in Fig. 3. We observe that new infrastructure segments typically appear as dead-end streets (culs-de-sac), as the minimal edge set needed to connect a collection of nodes will always yield a tree graph. A proof of this feature of the optimal solutions is given in section SE. Analogous tree configurations result from minimizing energy dissipation in fluid flows, a principle used to derive optimal transportation networks in river basins (*26*) and vascular systems (*27*).

For these reasons, the optimal solution corresponding to the absolute minimum amount of construction is interesting mathematically but is typically impractical for two main reasons: (i) for large neighborhoods, the minimal solution is difficult to find algorithmically because of the discrete combinatorial nature of the problem, which results in large algorithmic complexity for the search, and (ii) other local social, physical, and economic considerations imply that this optimal solution may not be the most desirable access configuration for local stakeholders (see discussion in sections SD and SE).

To deal with these issues, we generalize the search to a statistical optimization problem. This means that instead of finding the strict minimum access configuration, we find a set of access configurations that render the block universally accessible but use small additional amounts of construction. These can be sampled statistically from an ensemble of access configurations that render the block accessible with their total mean length, *L*(*U*), penalized via the introduction of parameters playing a role analogous to temperature in statistical mechanics. This optimization problem makes use of methods of statistical physics by defining a probability distribution of neighborhood path configurations and sampling it using the Monte Carlo techniques (see section SD for details) (*28*). The possibility of generating diverse reblocking proposals is important because many local factors play a role in deciding implementable solutions, including the existence of incipient accesses and other forms of informal land use (see Discussion).

### Geometric optimization and access network efficiency

Having shown how city blocks can be made universally accessible via the solution of the constrained optimization problems discussed above, we now return to the issue of culs-de-sac. Even when we solve for a “low-temperature” ensemble of possible accesses, typical access network configurations will share the general features of the minimal solution as sets of branching dead-end streets and paths. But, access networks within developed neighborhoods seldom look like trees (*20*–*22*, *29*). A proliferation of culs-de-sac is not typical of most neighborhoods because it results in long distances over the network between places that are spatially nearby and may also cause congestion at the entrances (*15*). On the other hand, the deviation from a branching geometry for local accesses implies that, as neighborhoods develop, more accesses are built than are minimally necessary. These adaptations are, thus, not unique and depend on the nature and history of local land uses. For example, many planned suburban residential neighborhoods in the United States display copious numbers of cul-de-sacs, ostensibly for reasons of privacy (*30*), while commercial districts typically demand greater access.

To construct a systematic approach to these choices, we develop a second optimization problem dedicated to reducing travel costs (such as time and energy) between any two (already accessible) places (figs. S7 and S8) (*21*, *31*). To do this, we define a matrix, ℑ = {*T*_{ij}}, where *T*_{ij} is the minimal travel distance between places *i* and *j* over the existing access network (Fig. 3). Figure 3 (A and B; right) shows a block structure in the entries *T*_{ij}, which follows from the existence of dead ends after topological optimization. Thus, travel costs can be substantially reduced by proposing additional paths that typically bisect the block along adjoining dead ends (Fig. 3C). The marginal benefit of introducing additional infrastructure to generate through streets is large because it can markedly decrease average place-to-place travel distance (Fig. 3C).

As an illustration, these optimization strategies seek to find the sets of additional paths *l* that produce the largest marginal decrease in average travel costs d/d*l*. To create good candidates for d*l*, we systematically identify the least connected parcel, *p**, as that with the minimum ratio of geometric to travel distance within the block. This parcel always lies on a cul-de-sac. We optimally increase connectivity for *p** by building the shortest path d*l* connecting *p**’s points of access to the point of access of the parcel *p* with minimum geometric to travel distance ratio to *p**. This necessarily bisects the block, with the global effect that total travel distances for each parcel are reduced, and the value of is reduced (section SE and figs. S7 and S8).

This simple procedure can be repeated until the block is judged to be sufficiently connected (and, for example, dead ends are eliminated) or a budget is exhausted. It can also continue over time as land uses and preferences change, or vehicle use patterns change and congestion choke points evolve (*32*). The gradual transformation of path systems with many dead ends to new blocks agrees qualitatively with historical sequences of neighborhood development (fig. S9) (*14*, *33*, *34*), so that the processes formalized here provide a complete approach to the evolution of the local spatial fabric of cities.

## DISCUSSION

Urbanization trends throughout the world transform the nature of issues of human development into primarily urban problems. In most developing cities, informal settlements or slums comprise substantial parts of the population, in many cases its majority, especially in South Asia and Sub-Saharan Africa (*1*). Slums are diverse in their physical appearance, layout, type of location, and specific social, physical, and economic challenges, but they share the common characteristics of lack of accesses, absence of urban services, and unplanned land use and consequent detrimental impacts on social, economic, health, and environmental outcomes (see Figs. 1 and 2, and figs. S1 and S5 to S8 for several examples) (*1*, *6*–*10*).

The magnitude of this problem worldwide is enormous, but there is also increasing awareness of this issue and attempts to create the conditions for neighborhood and general urban development (*1*–*6*, *13*, *35*). The past Millennium Development Goals targeted significant improvements to the lives of 100 million slum dwellers worldwide (goal 7, target 11, also known as “Cities without Slums”). The new Sustainable Development Goals contain much more ambitious targets for the next two decades. In addition, substantial programs for informal settlement upgrading and resettlement are in development at the national level (*13*, *19*, *36*).

Reblocking and concomitant street access to all places within city blocks have a number of important spillover effects (*10*): It allows an incremental approach to neighborhood change, encourages participatory planning via enumeration and community mapping, improves the physical integration of slums in the formal city, assists in land regularization and security of tenure, and leads to higher revenues for the city. Thus, “streets become tools for social, economic, juridical and spatial integration of slums with the city (*10*).” While many important issues are context-dependent, new empirical evidence points to important general features of cities common to most poor or informal neighborhoods, such as the lack of services and infrastructure (*1*, *13*, *23*).

We formalized this problem by characterizing the general topology of cities—city block by city block—and thereby showing when specific neighborhoods can be diagnosed as missing accesses, as well as the difficulty (complexity) of such problem in each specific instance. This procedure allows us to characterize the urban fabric of any city from maps that include spatial parcels and access networks in a way that can be fully automated and taken to scale. We have then illustrated how the solutions of the two constrained optimization problems proposed here provide the means to efficiently connect each place in an informal neighborhood and gradually evolve the corresponding access network in response to socioeconomic change, as observed in the historical patterns of change in the urban fabric of many cities (fig. S9) (*34*).

It is interesting to note that the morphological transformations characterized here have a long history and are typical not only of cities but also of other complex systems where transport is mediated by networks. While topology is associated with necessary function, such as urban mobility and the ability of a locus of precipitation to flow to the ocean (*26*) or of blood to reach every cell in an organism (*27*), these networks and the places that they serve can be arranged in a continuous spectrum of variable shapes, associated with tradeoffs involving different physical dimensions (length and volume) and energy budgets.

For cities, we have shown that once each neighborhood becomes universally accessible, all cities become topologically equivalent (up to the number of blocks). This means that buildings and infrastructure networks can—in principle at least—be reshaped continuously as a city evolves without loss of essential function (section SF). It also means that any section of one city, with the same number of blocks, can be deformed onto another. In this way, parts of Baghdad can be reshaped into Beijing, and quartiers of Paris can be deformed into New York City blocks, just like different river basins or individual vasculatures vary in their detailed geometry but display the same topology.

Over the next couple of decades, it is estimated that infrastructure investments will need to exceed $1 trillion/year in developing nations to meet international development goals, with the majority in poor areas of developing cities. Slum upgrading is a key strategy for achieving these goals (*1*, *23*), with infrastructure costs accounting for about 50% of the total (*25*). Efficient reblocking is an essential part of these transformations because the most important determinant of the cost of building or upgrading urban infrastructure is the existence and layout of the access network. By identifying and formalizing the essence of the spatial transformations necessary for neighborhood evolution, the methods proposed here increase the benefit-cost ratio for infrastructure provision [currently ~3 for water and sanitation (*25*)] and markedly accelerate—from months to minutes—most technical aspects of creating viable reblocking plans. This enables nontechnical stakeholders to focus their time and effort on the socioeconomic tradeoffs of alternative layouts [leading to savings of up to 30% (*23*)] and creates precise digital maps that can formalize land uses and property records, facilitating political and civic coordination and further local development.

We have explored spatial solutions based on building street plans into underserviced neighborhoods, with little attention toward socioeconomic heterogeneity or inequality among households. This is a common practice based on extensive enumerations of the neighborhood prior to reblocking (*5*), which typically lock in the existing status quo in terms of residential land uses (for example, relative plot sizes). However, within-community distributional issues are often a substantial hurdle to any reblocking effort as different households may benefit in different ways from this type of neighborhood upgrading: for example, by ending up with larger or more attractive sites (*37*). These issues are hard to foresee in each specific case and must, in our view, be resolved by common agreement between residents and their city, using this type of tool not as a prescription for a new plan but rather as a way to collectively compare possible solutions and negotiate outcomes that are at once fair and efficient.

As we write, the formal procedures introduced in this paper are being applied to informal settlements of Cape Town and Mumbai to help address issues related to their formalization and the introduction of basic services. These processes are led by neighborhood communities who, in coordination with their local governments, map their informal settlements and produce reblocking proposals enabled by the methods proposed here, aligned with their preferences, priorities, and budgets [for example, (*5*)]. We believe that only the current convergence of science, technology, and contextually appropriate people-centric design practices can deliver the necessary fast change in the millions of neighborhoods worldwide that require upgrading to deliver on the promise of urbanization to eliminate humanity’s greatest sustainable development challenges over the next few decades.

## MATERIALS AND METHODS

### Data and experimental design

We assembled a large and diverse set of detailed urban maps to demonstrate the generality of the topological characteristics of cities, as described in the main text and detailed below. These cover historical cases and contemporary cities across very different levels of socioeconomic development, distinct cultures, and geographies.

To do this, we assembled a large corpus of detailed urban maps based on historical cadastral records, modern tax assessor maps, community-generated structural-level maps, and digitized and georeferenced satellite imagery and aerial photography. Because of space constraints, only a few of these are shown in the main paper. Here, we provide additional details concerning sources and the creation of georeferenced digital maps.

The data for Figs. 1D and 3A and figs. S5 to S7 refer to an informal settlement in Epworth (Harare, Zimbabwe) (*38*). Epworth maps and data were created by neighborhood resident community members in collaboration with the Zimbabwe Homeless People’s Federation and Dialogue on Shelter (http://dialogueonshelter.co.zw), which are federations of the Slum/Shack Dwellers International (http://knowyourcity.info and https://spark.adobe.com/page/lPGu5drMG5Hba/), who also georeferenced and digitized the map. These organizations have developed and adopted a now widespread process in developing cities of collecting various types of detailed neighborhood data to facilitate a community-driven household enumeration and reblocking process (see section SB). A larger portion of the neighborhood map is shown in fig. S6. We verified these maps in terms of georeferencing of parcels, blocks, and roads against satellite images.

The parcels in Khayelitsha, a neighborhood of Cape Town, South Africa (see https://en.wikipedia.org/wiki/Khayelitsha) shown in Figs. 2 and 3 (B and C) and fig. S8, were identified on the basis of manual digitization of structures visible from aerial photography (Fig. 1A) following a site visit by our team (including two of the authors, J.H. and L.M.A.B.) in June 2014 in collaboration with a data collection exercise by Community Organisation Resource Centre (http://sasdialliance.org.za/about/corc/). The locations of the urban services shown in Fig. 1A were also collected during the June 2014 site visit.

The original map on which fig. S1 was based was created to support the Rajiv Grand Project, a proposed widening of the Mankhurd-Belapur railway line in Mumbai, India. This map was jointly verified by the community residents and the Railway Authority in 1995 and digitized by Eliza Harrison in May 2015. This figure reflected the verified parcel geometry from 1995, although a significant number of new structures have been constructed in the settlement since then. The new construction was reported by community residents and easily verified through an inspection of satellite imagery and a site visit by authors C.B., J.H., and L.M.A.B. in January 2015.

The map of Las Vegas, NV, in fig. S3 was based on the Clark County Tax Assessor’s records [Secured Tax Roll (2012); www.clarkcountynv.gov/Depts/assessor/Services/Pages/AssessorDataFiles.aspx], available for academic use through a public records request. The data used to create Fig. 1B are based on the New York City Digital Tax Map [Department of Finance, Digital Tax Map (2015), available at http://maps.nyc.gov/taxmap/map.htm]. Data for the parcels, blocks, and roads for the entire city are available in digital georeferenced form. These types of parcel-level maps are increasingly common in developed nations, even though many of these records are not in the public domain and must be obtained from local authorities on a case-by-case basis.

New kinds of open source mapping data, such as OpenStreetMap, become increasingly common data sources for large-scale comparative studies of urban form. At this time, the OpenStreetMap community has not reached a consensus on whether parcel-level data should be included on the platform, even as it becomes increasingly common. This is because of the many heterogeneous data sources and concerns about parcel data validity and quality. For example, parcel layouts change very quickly in rapidly growing cities, and so the maps may quickly become outdated or inaccurate. There is yet also no consensus around what metadata should be attached to a parcel.

The data shown in Fig. 1C and fig. S9 were obtained from one of the earliest extensive parcel-level maps of Prague (Czech Republic), completed in 1842. It was scanned into digital form and georeferenced by the City Development Authority of Prague in 2012. A small part of this original map is shown in fig. S9, overlaid with our identification of the parcels for a single block, as shown in Fig. 1C. Courtyards that are not accessible by road were included in the space of each individual parcel, while open spaces that are accessible by road were included in the access system. Parcel delineations for major buildings and roads that were constructed before 1842 and are still extant today were used to verify the scale and georeference of the original map.

In addition, we have obtained, created or digitized, and georeferenced many other maps of formal and informal neighborhoods across the world, including in large dense cities such as Rio de Janeiro and São Paulo (where city authorities have mapped most favela boundaries), Mexico City (from research surveys), and Kampala, Lusaka, Nairobi, and Mumbai from a variety of local sources. All these maps and cities display the general quantitative features described in the paper.

### Map statistical analysis

At present, many different methods become available for generating parcel-level maps of a city and neighborhood, from those created by resident communities and nongovernmental organizations to official cadastral maps, for example, linked to property records and taxation. Maps created by manual inspection of remote sensing imagery at adequate resolutions or via machine learning techniques (*39*) are also increasingly common because of new data and new analysis tools.

The convergence and cross-verification of all these methods, much facilitated by georeferencing of data, make possible new advances in our detailed understanding of the changes of physical space in cities in relation to people’s socioeconomic condition and its transformation. Our emphasis here is to demonstrate how some of these practical possibilities require a systematic formal (theoretical and mathematical) understanding of these transformations. The methods introduced in this paper are capable of responding in general and flexible ways to parcel-level maps from almost any source and make sense of their topology and geometry through comparative quantitative analysis.

## SUPPLEMENTARY MATERIALS

Supplementary material for this article is available at http://advances.sciencemag.org/cgi/content/full/4/8/eaar4644/DC1

Supplementary Text

Section SA. Topology of access systems

Section SB. Topology of city blocks

Section SC. City block topological theorems

Section SD. Topological optimization: Minimal neighborhood reblocking

Section SE. Geometric optimization: Travel costs versus road construction

Section SF. The topology of places is equivalent to the topology of the access system

Fig. S1. Phule Nagar (Mumbai, India) path width.

Fig. S2. Topological constructs for the systematic analysis of urban topology.

Fig. S3. Las Vegas (NV, USA) access system and access network.

Fig. S4. Schematic bridge graph retraction.

Fig. S5. Epworth (Harare, Zimbabwe) minimal reblocking.

Fig. S6. Epworth (Harare, Zimbabwe) before and after reblocking.

Fig. S7. Epworth (Harare, Zimbabwe): Geometric optimization and travel cost matrices.

Fig. S8. Khayelitsha (Cape Town, South Africa): Reblocking and travel cost matrices.

Fig. S9. Prague cadastral map and block parcel layout.

Movie S1. Urban topological invariance.

This is an open-access article distributed under the terms of the Creative Commons Attribution-NonCommercial license, which permits use, distribution, and reproduction in any medium, so long as the resultant use is **not** for commercial advantage and provided the original work is properly cited.

## REFERENCES AND NOTES

**Acknowledgments:**We thank J. Lobo, J. Miller, and members of Slum Dwellers International in Zimbabwe, South Africa, and India for discussions and comments and the Arizona State University/Santa Fe Institute Center for Biosocial Complex Systems for partial support. We acknowledge the working paper by E. L. Moreno, “Slums of the World: The Face of Urban Poverty in the New Millennium?: Monitoring the Millennium Development Goal, Target 11—World-Wide Slum Dweller Estimation,” published by UN-Habitat (Nairobi, Kenya, 2003). This is the source of many estimates of current and future slum populations. This research was partially funded by the Bill & Melinda Gates Foundation (grant OPP1076282), the MacArthur Foundation (grant 13-105749-000-USP), the Army Research Office Minerva program (grant no. W911NF1210097), and the Laboratory Directed Research and Development Program of Oak Ridge National Laboratory, managed by the UT-Battelle, LLC, for the U.S. Department of Energy. This paper builds on a Santa Fe Institute working paper title “The Topology of Cities” by Brelsford

*et al*., which can be found at www.santafe.edu/research/results/working-papers/the-topology-of-cities.

**Author contributions:**C.B. and L.M.A.B. designed the research. C.B., T.M., and L.M.A.B. performed the research. C.B., T.M., J.H., and L.M.A.B. contributed new analytic tools. C.B. analyzed the data. C.B., T.M., and L.M.A.B. wrote the paper.

**Competing interests:**The authors declare that they have no competing interests.

**Data and materials availability:**All data needed to evaluate the conclusions in the paper are present in the paper and/or the Supplementary Materials. Demonstrations, data, code, and a selection of maps are available at http://openreblock.org and https://github.com/brelsford/topology. Additional data related to this paper may be requested from the authors.

- Copyright © 2018 The Authors, some rights reserved; exclusive licensee American Association for the Advancement of Science. No claim to original U.S. Government Works. Distributed under a Creative Commons Attribution NonCommercial License 4.0 (CC BY-NC).