Raphaël Chattot
email: raphael.chattot@grenoble-inp.org

Isaac Martens

Marta Mirolo

Michal Ronovsky

Florian Russello

Helena Isern

Guillaume Braesch

Elisabeth Hornberger

Peter Strasser

Eric Sibert

Helena Isern Herrera

Marian Chatenet

Veijo Honkimäki

Jakub Drnec

Electrochemical Strain Dynamics in Noble Metal Nanocatalysts

Keywords: Nanocatalysts, Operando X-ray Diffraction, Strain, Palladium Hydrides, Platinum Adsorption Trends

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Surface science has driven the development of commercial nanocatalysts for energy conversion and storage applications, by establishing the electronic descriptors that rationalize or even predict the activity of metallic surfaces for numerous reactions in the frame of the Sabatier principle: the ability of the surface to bind adsorbates and the strength of the bonds define the reaction thermodynamics and kinetics [START_REF] Henry | Surface Studies of Supported Model Catalysts[END_REF][START_REF] Markovic | Surface Science Studies of Model Fuel Cell Electrocatalysts[END_REF][START_REF] Nørskov | Origin of the Overpotential for Oxygen Reduction at a Fuel-Cell Cathode[END_REF][START_REF] Jiao | Design of Electrocatalysts for Oxygen-and Hydrogen-Involving Energy Conversion Reactions[END_REF][START_REF] Nørskov | Towards the Computational Design of Solid Catalysts[END_REF] . This seminal knowledge has allowed tremendous improvements in electrocatalytic materials according to the 'catalysts-by-design' [START_REF] Hammes-Schiffer | Catalysts by Design: The Power of Theory[END_REF] approach, where catalytic performance is tailored by the surface crystallographic structure and chemical composition [START_REF] Zhao | Theory-Guided Design of Catalytic Materials Using Scaling Relationships and Reactivity Descriptors[END_REF][START_REF] Mistry | Nanostructured Electrocatalysts with Tunable Activity and Selectivity[END_REF][START_REF] Calle-Vallejo | Tailoring the Catalytic Activity of Electrodes with Monolayer Amounts of Foreign Metals[END_REF] . Tacitly, this approach relies on the supposed unilateral causal relationship between the fixed nanocatalyst structure and the electrocatalyzed reaction mechanism/kinetics. However, various opposite relations, i.e. the catalyst structure alteration by the (electro)chemical environment, exist. Among them, irreversible degradation processes has received a lot of attention. In fact, even the most noble metal based catalysts, such as Platinum (Pt) or Palladium (Pd) are subject to corrosion over the long term in the harsh conditions of proton (or anion) exchange membrane fuel cell (PEMFC, AEMFC) cathode and proton (or anion) exchange membrane water electrolyzer (PEMWE, AEMWE) anode [START_REF] Cherevko | Dissolution of Noble Metals during Oxygen Evolution in Acidic Media[END_REF][START_REF] Lafforgue | Selected Review of the Degradation of Pt and Pd-Based Carbon-Supported Electrocatalysts for Alkaline Fuel Cells: Towards Mechanisms of Degradation[END_REF] , thus compromising the lifetime of those systems. In these particular cases, the electrochemical adsorption trend of oxygenated species does not only define the catalyst activity [START_REF] Nørskov | Origin of the Overpotential for Oxygen Reduction at a Fuel-Cell Cathode[END_REF] but also its stability against dissolution according to the place exchange mechanism [START_REF] You | Place-Exchange Mechanism of Pt(111) Oxidation/Reduction as Observed by Synchrotron X-Ray Scattering[END_REF] .

In addition, reversible structural modifications can also be observed. For example, (electrochemical) absorption of hydrogen (H) into the bulk of Pd (nano)crystal is known to induce sharp Pd lattice expansion, in the form of a phase transition [START_REF] Lewis | The Hydrides of Palladium and Palladium Alloys[END_REF][START_REF] Lewis | The Palladium-Hydrogen System: Structures near Phase Transition and Critical Points[END_REF][START_REF] Scholtus | Hysteresis in the Palladium-Hydrogen System[END_REF][START_REF] Schwarz | Thermodynamics of Open Two-Phase Systems with Coherent Interfaces: Application to Metal-Hydrogen Systems[END_REF] . As a result, the strain in Pd is classically used as a direct quantitative descriptor of hydrogen absorbed (the H:Pd ratio) [START_REF] Eastman | Narrowing of the Palladium-Hydrogen Miscibility Gap in Nanocrystalline Palladium[END_REF][START_REF] Bugaev | Core-Shell Structure of Palladium Hydride Nanoparticles Revealed by Combined X-Ray Absorption Spectroscopy and X-Ray Diffraction[END_REF][START_REF] Benck | Producing High Concentrations of Hydrogen in Palladium via Electrochemical Insertion from Aqueous and Solid Electrolytes[END_REF][START_REF] Johnson | Facets and Vertices Regulate Hydrogen Uptake and Release in Palladium Nanocrystals[END_REF] , from the established near linear relationship between these two entities [START_REF] Benck | Producing High Concentrations of Hydrogen in Palladium via Electrochemical Insertion from Aqueous and Solid Electrolytes[END_REF] . Lastly, surface X-ray diffraction on single crystals revealed the impact of electrochemical surface adsorption process on crystal strain [START_REF] Nakamura | Effect of Non-Specifically Adsorbed Ions on the Surface Oxidation of Pt(111)[END_REF][START_REF] Kondo | Potential-Dependent Structures and Potential-Induced Structure Changes at Pt(111) Single-Crystal Electrode/Sulfuric and Perchloric Acid Interfaces in the Potential Region between Hydrogen Underpotential Deposition and Surface Oxide Formation by in Situ Su[END_REF][START_REF] Liu | Layering and Ordering in Electrochemical Double Layers[END_REF][START_REF] Liu | X-Ray Crystal Truncation Rod Studies of Surface Oxidation and Reduction on Pt(111)[END_REF] . Compared to bulk absorption, surface adsorption produces a much subtler effect since the interplanar distances from only the 2 or 3 first monolayers were found to be impacted by various adsorbates. However, despite the extremely high surface-to-volume ratio of nanomaterials and the urgent need for experimental techniques able to monitor the electrochemical adsorption trends of practical catalytic materials during operation, in-depth investigation of nanocatalyst 'electrochemical strain' has never been performed.

In this contribution, we use the light from the new 4 th generation Extremely Brilliant Source of the European Synchrotron Radiation Facility (ESRF-EBS, Grenoble, France) to investigate the structural evolution of device-relevant, carbon-supported Pd and Pt nanocatalysts during various cyclic voltammetry experiments in liquid electrolytes (acid and alkaline). The brilliance and high-energy of the employed Xrays reveal catalysts microstructural information with unprecedented combined quality and temporal resolution for operando measurements. The first discovery is that, contrary to the current knowledge, the strain in carbon-supported Pd (Pd/C) and Pt (Pt/C) nanoparticles is permanently affected by the electrochemical environment. The impact of both electrochemical bulk hydrogen absorption and surface adsorption processes are then investigated separately on Pd and Pt, respectively. Analysis of our structural data provide new insights in the mechanism of electroabsorbed hydrogen-induced phase transition in the Pd-H system and reveal the adsorption trends of Pt. Subsequent comparison between Pd and Pt shows absorption and adsorption phenomena produce close but distinctive structural changes allowing their disentanglement from strain measurements. Finally, further insights on the atomistic origin of electrochemical strain are presented, and its potential implication in electrocatalysis is discussed. These new results extend our understanding of noble nanomaterials behavior in electrochemical environments and provide versatile experimental access to reactivity and stability descriptors of practical nanocatalysts, operando. for E ≤ 0.40 V vs. RHE) recalls the apparent violation of the Gibbs phase rule observed in the classical hydrogen pressure-composition isotherm for the Pd-H system in the gas phase [START_REF] Lewis | The Palladium-Hydrogen System: Structures near Phase Transition and Critical Points[END_REF] . In agreement with these former results, hydride formation appears thermodynamically-disfavored, with here a value of at least 100 mV overpotential compared to hydrogen desorption. Corresponding hydrogen content (H:Pd ratio) in the PdH x -β phase can be estimated from the measured lattice constant and the calibration reported by Benck et al. [START_REF] Benck | Producing High Concentrations of Hydrogen in Palladium via Electrochemical Insertion from Aqueous and Solid Electrolytes[END_REF] , and the values are indicated in Figure 3.a as top axis. Note the maximum H:Pd ratio of 0.65 on Pd nanoparticles obtained in these experimental conditions at a potential of -200 mV vs. RHE would require H 2 pressure in the order of 100 MPa in the gas phase at room temperature [START_REF] Benck | Producing High Concentrations of Hydrogen in Palladium via Electrochemical Insertion from Aqueous and Solid Electrolytes[END_REF][START_REF] Yamauchi | Hydrogen Storage Mediated by Pd and Pt Nanoparticles[END_REF] and cyclic voltammetry. This can be rationalized by slow hydrogen desorption kinetics that was reported to be dependent on both nanoparticle facets [START_REF] Johnson | Facets and Vertices Regulate Hydrogen Uptake and Release in Palladium Nanocrystals[END_REF] and alkali metal cation [START_REF] Czerwinski | The Absorption of Hydrogen and Deuterium in Thin Palladium Electrodes. Part II: Basic Solutions[END_REF] .

RESULTS AND DISCUSSION

Unveiling electrochemical strain dynamics in noble metal nanocatalysts during cyclic voltammetry experiments

More insights into the phase transition mechanism can be provided by Rietveld refinement.

Electrochemical strain on Pt reveals its adsorption trends operando

It is well established from surface X-ray diffraction experiments on single crystals that, at fixed bulk properties, interplanar distances between the three first surface atomic layers are sensitive to adsorption processes [START_REF] Nakamura | Effect of Non-Specifically Adsorbed Ions on the Surface Oxidation of Pt(111)[END_REF][START_REF] Kondo | Potential-Dependent Structures and Potential-Induced Structure Changes at Pt(111) Single-Crystal Electrode/Sulfuric and Perchloric Acid Interfaces in the Potential Region between Hydrogen Underpotential Deposition and Surface Oxide Formation by in Situ Su[END_REF][START_REF] Liu | Layering and Ordering in Electrochemical Double Layers[END_REF][START_REF] Liu | X-Ray Crystal Truncation Rod Studies of Surface Oxidation and Reduction on Pt(111)[END_REF] . Clearly, the enhanced surface-to-volume ratio of metal nanoparticles induces changes in the average lattice constant during adsorption processes that can be measured from simple powder X-ray diffraction experiments. This strongly suggests that the electrochemical strain is a direct consequence of charge adsorption processes on the surface of the nanoparticles: the lattice constant is minimum at the pztc and increases as adsorption of positively or negatively charged species proceeds (at electrode potential below or above the pztc, respectively). Using a method introduced by Uchida et al. [START_REF] Uchida | Electrochemical Quartz Crystal Microbalance Study of Copper Adatoms on Gold Electrodes Part II. Further Discussion on the Specific Adsorption of Anions from Solutions of Perchloric and Sulfuric Acid[END_REF] exploiting the linear correlation existing between Pt electrode mass variation and the measured charge transfer (including the double layer current), numerous studies [START_REF] Gloaguen | Electrochemical Quartz Crystal Microbalance Study of the Hydrogen Underpotential Deposition at a Pt Electrode[END_REF][START_REF] Santos | Study of Anion Adsorption on Polycrystalline Pt by Electrochemical Quartz Crystal Microbalance[END_REF][START_REF] Jerkiewicz | Surface-Oxide Growth at Platinum Electrodes in Aqueous H2SO 4 Reexamination of Its Mechanism through Combined Cyclic-Voltammetry, Electrochemical Quartz-Crystal Nanobalance, and Auger Electron Spectroscopy Measurements[END_REF][START_REF] Garrick | Characterizing Electrolyte and Platinum Interface in PEM Fuel Cells Using CO Displacement[END_REF] identified the adsorption of water, OH -, and anions, or of the ionomer (if any) in both HClO 4 and H 2 SO 4 electrolytes. Here, we show in Figure 4.d that a robust linear relationship also exists between the (relative) variation of the lattice constant and the measured charge transfer for both potential sweep directions from the pztc and 1.0 V vs. RHE. This discovery is of primary importance because it suggests the experimentally accessible lattice constant can be a structural descriptor of nanoparticles adsorption trends. Most importantly, contrary to the bulk electrode overall mass, this descriptor is an intrinsic property of the catalyst alone, which can be measured directly on practical nanocatalysts during operation, beyond any current experimental approaches [START_REF] Bergmann | Operando Insights into Nanoparticle Transformations during Catalysis[END_REF] . Despite not explicitly provided from this method at this stage, information on the chemical nature of the adsorbates is likely encoded in the slope of the trend in Figure 4.d, which calls for a theoretical formalization of the reported phenomenon. Still, for adsorption, the surface electrical charge density is directly related to surface atoms average oxidation state, which gives information on possible adsorbates, as discussed below.

Fingerprints of absorption, adsorption and Faradaic processes on electrochemical strain

The present results make clear that both absorption and adsorption processes contribute to nanoparticles lattice expansion. Comparing trends on Pd and Pt in alkaline electrolyte (Figure 5) shows that these processes, together with Faradaic reactions (such as hydrogen evolution), can still be distinguished from each other. To clarify the comparison, however, the low potential vertex of the cyclic voltammetry in this dedicated experiment was up-shifted to 0.00 V vs. RHE for Pd to prevent the formation of the PdH x -β phase (while hydrogen absorption still occurs in PdH x -α).

Atomistic description of electrochemical strain and its implication in electrocatalysis

Surface strain in nanocatalysts has so important consequences on their catalytic properties, that 'strainengineering' has emerged as a fruitful approach toward the design of more active materials for a wide range of applications [START_REF] Luo | Strain-Controlled Electrocatalysis on Multimetallic Nanomaterials[END_REF][START_REF] Strasser | Lattice-Strain Control of the Activity in Dealloyed Core-Shell Fuel Cell Catalysts[END_REF][START_REF] Xia | Strain Engineering of Metal-Based Nanomaterials for Energy Electrocatalysis[END_REF] . In that context, more than a convenient characterization tool allowing probing nanocatalysts adsorption trends operando, the presented electrochemical strain may at least partially control the revealed adsorption trends. Consequently, how much the systematic structural changes dynamics observed here are predicted to affect the electrocatalytic properties is a fundamental question.

We take the oxygen reduction reaction (ORR) as an example reaction using our dataset on Pt/C thin-film catalyst measured in model 0.1 M HClO 4 conditions and presented in Figure 4. The influence of Pt surface strain on its ORR performance is largely documented [START_REF] Luo | Strain-Controlled Electrocatalysis on Multimetallic Nanomaterials[END_REF][START_REF] Strasser | Lattice-Strain Control of the Activity in Dealloyed Core-Shell Fuel Cell Catalysts[END_REF][START_REF] Xia | Strain Engineering of Metal-Based Nanomaterials for Energy Electrocatalysis[END_REF] , and implementing moderate compressive strain is shown desirable to maximize the ORR activity by optimizing hydroxyl groups adsorption strength. The tensile strain observed here during adsorption, however, should favor site poisoning and be detrimental to the ORR (excepted some specific reported cases [START_REF] Luo | Strain-Controlled Electrocatalysis on Multimetallic Nanomaterials[END_REF] ). As shown in Figure 4.b-d, the measured global tensile strain does not exceed 0.12 % in the range 0.05 ≤ E ≤ 1.0 V vs. RHE relatively to the structure of Pt at the pztc. Rationalizing this strain amplitude value in the frame of the ORR electrocatalysis, however, requires discussing the surface and absolute strain (or at least compared to a model reference state). The near-constant microstrain values (representative of lattice constant heterogeneity) measured during cyclic voltammetry experiment displayed in Figure 6.a provide fundamental insights on the atomistic origin of the electrochemical strain: the latter is varying homogeneously in the nanoparticle. Consequently, the observed changes in the lattice can be attributed to the whole nanoparticle without distinction of the surface from the bulk. Note the near-constant but positive values of microstrain recorded indicate 'native' local heterogeneities exist in the lattice (defects such as grain boundaries [START_REF] Chattot | Beyond Strain and Ligand Effects: Microstrain-Induced Enhancement of the Oxygen Reduction Reaction Kinetics on Various PtNi/C Nanostructures[END_REF] , stress round steps, edges or from nanoparticle-support interactions 45 etc.).

Interestingly, the slight microstrain decrease observed in the H UPD potential region attests of very good sensitivity of this parameter, since hydrogen adsorption is known to produce reversible step-edges roughening of Pt surfaces during such cyclic voltammetry experiments [START_REF] Mccrum | Hydrogen-Induced Step-Edge Roughening of Platinum Electrode Surfaces[END_REF] . The ability of nanoparticles to accommodate the surface adsorbate-induced strain with the complete bulk is a first distinction compared to single crystals. As shown in Figure 6.b, the in situ surface XRD data from Kondo et al. [START_REF] Kondo | Potential-Dependent Structures and Potential-Induced Structure Changes at Pt(111) Single-Crystal Electrode/Sulfuric and Perchloric Acid Interfaces in the Potential Region between Hydrogen Underpotential Deposition and Surface Oxide Formation by in Situ Su[END_REF] (blue curves), recorded in similar conditions of this study show a strong tensile unilateral strain gradient between the two first interplanar distances of Pt(111) single crystal (d 12 and d 23 , for first and second, respectively) during hydrogen adsorption. Note the third interatomic distance was found not modified compared with the bulk. The second distinctive feature concerns the potential region of interest for the ORR: whereas the adsorption of hydroxyl groups is found to be completely relax Pt(111) surface between 0.75 ≤ E ≤ 0.9 V vs. RHE, this is where the strain dynamics in nanoparticles is the more pronounced (see Figure 4.b-c). Since this strain can be attributed to the surface (and bulk) of the nanoparticles, its impact on ORR can be estimated. The non-conventional representation of this DFT trend with linear ORR activity axis helps realizing that, however, the impact of only 0.1 % overall compressive strain loss due to the electrochemical tensile strain contribution at E= 0.90 V vs. RHE would not produce the same effect on ORR activity depending on the catalyst initial position on the curve. In the case of the present pure Pt nanoparticles, this constitutes only a 0.26-fold difference in activity, whereas a catalyst a priori located at the apex of the curve would lose 3.5 unit of enhancement factor. Besides, quantification of electrochemical tensile strain on more advanced 'strained-by-design' and/or shape-controlled multimetallic materials is still to be performed. between the bulk lattice of Pt nanoparticles and oxides surface coverage. Since the latter is known to be a descriptor of catalysts activity toward numerous reactions (oxygen reduction and fuel oxidation) and stability (oxidation and dissolution), the measurement of the lattice parameter according to our proposed approach allows experimental access to these descriptors in device-relevant sample environments operando. This constitutes a main advantage compared to spectroscopic techniques and is foreseen to find a wide range of applications. Fourthly, comparing trends observed on Pd/C and Pt/C shows that adsorption and absorption processes have distinct impacts on the bulk lattice constant expansion. Such fingerprints allow disentangling the two processes from each other in a general fashion. Finally, since the electronic structure (d-band centre) of the catalytic sites is likely impacted by the observed strain dynamics, we provided a more precise atomistic description of this strain in the case of Pt in perchloric acid electrolyte. Notably, we showed the strain dynamics proceeds homogeneously in the nanoparticles, which means the surface strain is known in a potential resolved fashion. Taking the ORR as an exemplary reaction, and in light of previous reports, we showed the adsorbate-induced tensile strain must not significantly degrade the ORR performance in the case of pure Pt nanoparticles. However, this strain dynamics is currently overlooked by the theoretical models driving the catalyst-by-design approach of more advanced nanocatalysts, from which the trends in electrochemical strain remain unknown.

ASSOCIATED CONTENT

Supporting Information: Details and methods about the electrocatalysts used, electrochemical measurements, synchrotron wide-angle X-ray scattering measurements, Rietveld refinement and correction of microstructural data from nanoparticle size.

through grant 03XP0251 (''KorrZellKat''). P.S. also acknowledges partial funding by the Alexander von Humboldt Foundation.

Figure 1 .

 1 Figure 1.a shows a typical wide-angle X-ray scattering (WAXS) dataset obtained during cyclic

Figure 1 .

 1 Figure 1. New light on Pd nanoparticles during cyclic voltammetry. a) 3D representation and corresponding 2D projection of WAXS patterns intensities (1 over 20) plotted as a function of time and the momentum transfer Q recorded during Pd cyclic voltammetry experiment in N 2 -purged 0.1 M NaOH electrolyte at room temperature. The evolutions of the electrochemical potential applied and measured electric current are also represented on the same time scale; b) surface plot focus on a narrow Q window showing the full time resolution evolution of the two phases (Pd, or PdH x -α and PdH x -)[220] reflections. In b), the Q scale (left) is

Figure 1 )

 1 , and result in two distinct lattice constants and scale factors values (Figure 2.c). The Pd, or PdH x -α phase corresponds to Pd when no or few hydrogen atoms are inserted in octahedral interstitial positions and PdH x -when larger number of hydrogen atoms are inserted in octahedral interstitial positions. The regions corresponding to the existence and co-existence of the different PdH x phases revealed by their scale factors are indicated in the colored cyclic voltammogram (Figure 2.a). Whereas Figure 2.d reveals that adsorption and desorption of hydrogen produce rather potential-reversible variation of Pt lattice constant and preserve the nanoparticles coherence (constant and maximum scale factor), the phase transitions PdH x appear irreversible with the potential. In the following, we will sequentially focus on the electrochemical strain from (i) the electrochemical hydrogen absorption on Pd and (ii) the hydrogen, anions and oxides adsorption on Pt, before discussing the complete picture of adsorption and/or absorption processes on both Pd and Pt.

Figure 2 :

 2 Figure 2: High time resolution monitoring of nanocatalysts microstructures during cyclic voltammetry. Cyclic voltammogram of the (a) Pd/C and (b) Pt/C catalysts in N 2 -purged 0.1 M NaOH recorded at room temperature with a potential sweep rate of 5 mV s -1 ; potential-dependency of the relative lattice constant variation (filled symbols, left axis) and relative scale factor (Bragg peaks area) variation (hollow symbols, right axis for the (c) Pd/C and (d) Pt/C catalysts. In a), the recorded electrical current is colored in cyan when only the phase Pd or PdH x -α is detected, in red when only the PdH x -β is detected and in blue when both PdH xα and PdH x -β are detected simultaneously. In c) the signals colored in cyan correspond to the Pd or PdH x -α

Figure 3

 3 Figure S5). As smaller particles complete both transitions faster than large ones[START_REF] Langhammer | Size-Dependent Kinetics of Hydriding and Dehydriding of Pd Nanoparticles[END_REF] , the remaining volume-

Figure 3 .

 3 Figure 3.b illustrates the present findings regarding the PdH x phase transition mechanism: the core-shell formation steps during absorption (panels (i) to (v)) are found reversible for desorption (panels

Figure 3 :

 3 Figure 3: Monitoring hydrogen absorption on Pd nanocatalyst: (a) PdH x phase transition lattice constants hysteresis at the steady state (square symbols interpolated by black lines) measured after 60 s hold at various potentials, superimposed with the data from cyclic voltammetry at 5 mV s -1 (circle symbols); b) evolution of coherent domain sizes as a function of time for the two phases transitions during cyclic voltammetry. In a), the H:Pd ratio in the PdH x -is deduced from the measured lattice parameter and the calibration trend from Ref 19 . In b) the deduced core-shell model evolution schematics for the phase transitions is presented, including the PdH x -(cyan), supersaturated PdH x -(dark cyan), undersaturated PdH x -(orange) and PdH x -(red) phases.

Figure 4 .Figure 4 .

 44 Figure 4.b and 4.c). This potential value corresponds to the potential of zero total charge (pztc) measured by Chen et al. from CO displacement experiments on non-preferentially shaped Pt nanoparticles 32 . The

Figure 4 :Figure 4 .

 44 Figure 4: Monitoring adsorption on Pt: (a) cyclic voltammograms (solid line) and first derivative of the lattice constant (dashed line) of Pt/C in N 2 -purged 0.1 M HClO 4 recorded at room temperature with a potential sweep rate of 5 mV s -1 ; associated relative lattice constant variation (orange) and electrical charge variation estimated from different electrical current integration methods (introducing weights for adsorbates and/or subtraction of the double layer current) as a function of (b) time and (c) electrode potential averaged along several potential cycles; (d) linear regression (dash line) between lattice constant variation and adsorbate-weighted full charge. In a) the grey box represents the estimation of the double layer on the cyclic voltammogram. The electrode was loaded with 25 and the WAXS measured in grazing incidence configuration. The Pt surface area was estimated from the double-layer corrected hydrogen desorption current coulometry (without weight), assuming a conversion factor of 210 μC . The reference lattice constant value of Pt is 3.9150 Å .The error bars represent the standard deviation associated with the refinement of the plotted parameters.

Figure 5 :

 5 Figure 5: Disentangling adsorption, absorption and Faradaic processes from their fingerprints on catalysts microstructure: (a) Size-corrected relative lattice constant variation and (b) size-corrected scale factor variation for Pd/C and Pt/C catalysts as a function of electrode potential; (c) size-corrected lattice constant variation as a function of 'H UPD ' normalized full charge during cyclic voltammetry in N 2 -saturated 0.1 M NaOH. In c) the 'H UPD ' is estimated from the electrical charge passed at the slope break in the lattice trends. The reference lattice constant values are 3.8890 Å and 3.9085 Å for Pd and Pt, respectively. The signals are displayed as scatter points (333 ms time resolution) and the error bars represent the standard deviation associated with the refinement of the plotted parameters. The electrodes were loaded with 1.45 and measured in transmission configuration.

Figure 5 .

 5 a and 5.b show the relative, sizecorrected evolutions of the lattice constants and scale factors, respectively, measured for the two materials during cyclic voltammetry. The proposed correction from the size consists of dividing the raw structural parameters values by the dispersion (the proportion of surface atoms, in %) and was found necessary when comparing two materials of different particle sizes[START_REF] Chattot | Beyond Strain and Ligand Effects: Microstrain-Induced Enhancement of the Oxygen Reduction Reaction Kinetics on Various PtNi/C Nanostructures[END_REF][START_REF] Chattot | Surface Distortion as a Unifying Concept and Descriptor in Oxygen Reduction Reaction Electrocatalysis[END_REF] (correction details are provided in the Supporting Information). In light of the lattice constant changes, Figure 5.a makes clear that in the 0.60 E 0.90 V vs. RHE potential window and these experimental conditions, Pt features lower oxides surface coverage than Pd (despite the smaller size of the Pt nanoparticles versus Pd ones, Figure S5), which signs the larger oxophillicity of Pd versus Pt. The size-corrected, relative scale factor losses plotted in Figure 5.b can be directly interpreted as the fraction of the surface undergoing place exchange amorphisation (in %). The value at 1.32 V vs. RHE is found higher for Pd (-92%), which results in larger irreversibility during the negative-going potential scan compared to Pt (-48%). As previously discussed, different lattice constant evolutions between Pd and Pt are observed during electrode polarization below E = 0.40 V vs. RHE. Especially, from Figure 5.a, bulk hydrogen absorption is found to produce more pronounced lattice constant expansion than surface adsorption. Finally, Figure 5.c shows the variation of the lattice constants versus the 'H UPD ' normalized charge. Since the H UPD region is not defined on the cyclic voltammograms in these experimental conditions (H 2 evolution/oxidation on Pt and bulk absorption/desorption on Pd), the values were estimated from the electrical charge passed at the slope break in the lattice constant variation between hydrogen adsorption and either hydrogen evolution on Pt or hydrogen absorption on Pd. These slope breaks consequently appear at the -1 vertical line in Figure 5.c. Below this limit, Pt catalyzes the hydrogen evolution with constant lattice expansion, whereas Pd undergoes hydrogen absorption. The viability of the approach consisting of disentangling hydrogen adsorption from absorption and evolution from their impact on the lattice constant evolution trends is shown by its consistent impact on the oxidation trends. In fact, such H UPD estimation leads to a charge ratio at maximum oxidation very close to 1.48 for Pt and 1.92 for Pd (see dashed-lines). Attributing these charges to Pt and Pd translates into O ads (2-electron process) surface coverages of 0.48 and 0.92 for Pt and Pd (if the rest of the surface is covered by 1-electron process OH ads ), respectively. These values are the ones found from the O ads induced 41 place-exchange amorphisation revealed by the size-corrected relative scale factor losses in Figure 5.b. These convergent observations strongly support the proposed disentanglement of the different electrochemical processes based on the feedback of their distinct fingerprints on catalysts microstructures, as labeled in Figure 5.c.

Figure 6 .

 6 b displays a non-exhaustive literature data overview of the strain in different pure Pt surface systems: the above discussed operando Pt(111) single crystal data from Kondo et al. (blue curves), the ex situ data on Pt x Cu 100-x core-shell catalysts from Strasser et al.[START_REF] Strasser | Lattice-Strain Control of the Activity in Dealloyed Core-Shell Fuel Cell Catalysts[END_REF] (red lines), and the operando data on Pt nanoparticles investigated in this study (orange curve). The strain values are represented in absolute scale via the d 111 interplanar distances (left axis) and their associated values relative to the reference bulk Pt (right axis). As expected for nanoparticles due to their higher surface energy[START_REF] Medasani | Computational Study of the Surface Properties of Aluminum Nanoparticles[END_REF] , the plot first shows the Pt/C catalyst exhibits a slight compressive strain (negative values) over the whole potential range investigated. As schematized in Figure6.c, the compressed nanoparticles oscillate between the influences of surface tension and adsorbates, the latter may partially attenuate the former. But most of all, the comparative plot in Figure6.b makes clear the insignificance of the electrochemical strain variation amplitude (between c.a. -0.13% and -0.22 % in the landscape of strain-engineered nanocatalysts for the ORR. In fact, desirable nanocatalysts 'strained-bydesign' features ex-situ compressive strain values on the pure Pt surface one order of magnitude higher (see Pt x Cu 100-x core-shell catalysts). Especially, the density functional theory (DFT) calculations from previous contributions[START_REF] Strasser | Lattice-Strain Control of the Activity in Dealloyed Core-Shell Fuel Cell Catalysts[END_REF][START_REF] Stephens | Understanding the Electrocatalysis of Oxygen Reduction on Platinum and Its Alloys[END_REF] plotted in Figure6.d predict the optimal strain value of c.a. -1.75% to be implemented in surface Pt for maximized ORR performance (without contribution from other effects).

Figure 6 :

 6 Figure 6: Electrochemical strain in the ORR electrocatalysis landscape: (a) Microstrain values measured during cyclic voltammetry experiment of Pt/C catalyst plotted as a function of the electrode potential; (b) strain vs. electrode potential operando data for Pt(111) single crystal from Kondo et al. surface XRD measurements adapted from Ref 22 (blue curves) and Pt/C catalyst from this study (orange curve), strain in the Pt shell of a family of Pt x Cu 100-x core-shell catalysts measured ex situ from anomalous XRD adapted from Ref 43 ; (c) schematic showing the two opposite effects of surface tension and adsorbates formation on establishing the strain dynamics of a Pt nanoparticle in ORR environment; (d) experimental ORR activity as a function of compressive strain for the family of Pt x Cu 100-x core-shell catalysts of panel b) with theoretical trend estimated from DFT calculations in Ref 43 and further adapted by Ref 48 . In panel b) d 12 and d 23 are the first and second

  The first is a striking, previously unreported, continuous dynamics for both PdH x -α and PdH x -β lattices observed during the PdH x transitions. This challenges the commonly accepted concept of constant max and min (maximum/minimum insertion contents in the PdH x -α and PdH x -β phases, respectively) during phase transition. In fact, the positions of both sets of reflections from XRD were reported invariant during the two-phase transition regime by Eastman et al.[START_REF] Eastman | Narrowing of the Palladium-Hydrogen Miscibility Gap in Nanocrystalline Palladium[END_REF] ( max of 3.9079 ± 0.002 Å and min of 4.0167 ± 0.002 Å in the gas phase at room temperature), in total contradiction with the present observations captured with high time resolution. One

. In a dedicated study,

Benck et al.

could reach a H:Pd ratio as high as 0.96 on Pd thin film in 0.05 M H 2 SO 4 electrolyte at -1.5 V vs. RHE

[START_REF] Benck | Producing High Concentrations of Hydrogen in Palladium via Electrochemical Insertion from Aqueous and Solid Electrolytes[END_REF]

.

Superimposing the points recorded during cyclic voltammetry (circles) on the quasi-steady state plot (Figure

3

.a) reveals two significant features. must note that very similar conclusions to Eastman's could have been reached here from the lower time resolution dataset obtained at the quasi-steady state in Figure

3

.a, which shows an apparent max of 3.9033 ± 0.0006 Å and min of 4.0154 ± 0.002 Å. Figure

S3

shows selected WAXS patterns and associated Rietveld fits capturing the [220] reflections angular shifts for both phases during phasetransition. Our results support Lacher's idea introduced in 1937

[START_REF] Scholtus | Hysteresis in the Palladium-Hydrogen System[END_REF][START_REF] Lacher | A Theoretical Formula for the Solubility of Hydrogen in Palladium[END_REF]

proposing the possibility of metastable supersaturation of the PdH x -α phase and undersaturation of the PdH x -β phase during the transitions. According to the Schwarz and Khachaturyan theory

[START_REF] Schwarz | Thermodynamics of Open Two-Phase Systems with Coherent Interfaces: Application to Metal-Hydrogen Systems[END_REF][START_REF] Schwarz | Thermodynamics of Open Two-Phase Systems with Coherent Interfaces[END_REF]

now generally accepted to account for the Pd-H system hysteresis, this transient phenomenon is caused by the misfit-generated strain at the interface of the two phases with pronounced lattice mismatch. Our microstrain data, i.e. the local variations of the lattice constant within the individual phases, shown in Figure

S4

suggest this misfitgenerated strain is mostly accommodated by the PdH x -β phase. The second noticeable feature concerns the ~100 mV positive overpotential difference of the PdH x phase transition between steady state

ACKNOWLEDGEMENTS

G.B, E.S and M.C. thank the French National Research Agency (ANR, grant # ANR-16-CE05-0009-01) for the MobiDiC project. E.H. and P.S. thank the German Federal Ministry of Education and Research

AUTHOR INFORMATION


Zdeněk Dvořák

Daniel Gonçalves

Abhiruk Lahiri

Jane Tan

Torsten Ueckerdt

On Comparable Box Dimension

Keywords: 2012 ACM Subject Classification Theory of computation → Computational geometry; Mathematics of computing → Graphs and surfaces geometric graphs, minor-closed graph classes, treewidth fragility Digital Object Identifier 10.4230/LIPIcs.SoCG.2022.38

Two boxes in R d are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph G is the minimum integer d such that G can be represented as a touching graph of comparable axis-aligned boxes in R d . We show that proper minor-closed classes have bounded comparable box dimension and explore further properties of this notion.

Introduction

Given a system O of subsets of R d , we say that a graph G is a touching graph of objects from O if there exists a function f : V (G) → O (called a touching representation by objects from O) such that the interiors of f (u) and f (v) are disjoint for all distinct u, v ∈ V (G), and f (u) ∩ f (v) ̸ = ∅ if and only if uv ∈ E(G). Famously, Koebe [START_REF] Koebe | Kontaktprobleme der Konformen Abbildung[END_REF] proved that a graph is planar if and only if it is a touching graph of balls in R 2 . This result has motivated numerous strengthenings and variations (see [START_REF] Lovász | Graphs and Geometry[END_REF][START_REF] Sachs | Coin graphs, polyhedra, and conformal mapping[END_REF] for some classical examples); most relevantly for us, Felsner and Francis [START_REF] Felsner | Contact representations of planar graphs with cubes[END_REF] showed that every planar graph is a touching graph of cubes in R 3 . An attractive feature of touching representations is that it is possible to represent graph classes that are sparse (e.g., planar graphs, or more generally, graph classes with bounded expansion [START_REF] Nešetřil | Sparsity (Graphs, Structures, and Algorithms)[END_REF]). This is in contrast to general intersection representations where the represented class always includes arbitrarily large cliques. Of course, whether the class

38:2

On Comparable Box Dimension of touching graphs of objects from O is sparse or not depends on the particular system O. For example, all complete bipartite graphs K n,m are touching graphs of boxes in R 3 , where the vertices in one part are represented by m × 1 × 1 boxes and the vertices of the other part are represented by 1 × n × 1 boxes (throughout the paper, by box we always mean axis-aligned box, i.e., the Cartesian product of closed intervals of non-zero length). Dvořák, McCarty and Norin [START_REF] Dvořák | Sublinear separators in intersection graphs of convex shapes[END_REF] noticed that this issue disappears if we forbid such a combination of long and wide boxes. This condition can be expressed as follows. For two boxes B 1 and B 2 , we write B 1 ⊑ B 2 if B 2 contains a translate of B 1 . We say that B 1 and B 2 are comparable if B 1 ⊑ B 2 or B 2 ⊑ B 1 . A touching representation by comparable boxes of a graph G is a touching representation f by boxes such that for every u, v ∈ V (G), the boxes f (u) and f (v) are comparable. Let the comparable box dimension dim cb (G) of a graph G be the smallest integer d such that G has a touching representation by comparable boxes in R d . We remark that the comparable box dimension of every graph G is at most |V (G)|, see Section 3.1 for details. Then, for a class G of graphs, let dim cb (G) := sup{dim cb (G) : G ∈ G}. If the comparable box dimension of graphs in G is not bounded, we write dim cb (G) = ∞.

Dvořák, McCarty and Norin [START_REF] Dvořák | Sublinear separators in intersection graphs of convex shapes[END_REF] proved some basic properties of this notion. In particular, they showed that if a class G has finite comparable box dimension, then it has polynomial strong coloring numbers, which implies that G has strongly sublinear separators. They also provided an example showing that, for many functions h, the class of graphs with strong coloring numbers bounded by h has infinite comparable box dimension1 . Dvořák et al. [START_REF] Dvořák | Weak coloring numbers of intersection graphs[END_REF] proved that graphs of comparable box dimension 3 have exponential weak coloring numbers, giving the first natural graph class with polynomial strong coloring numbers and superpolynomial weak coloring numbers (the previous example is obtained by subdividing edges of every graph suitably many times [START_REF] Grohe | Coloring and covering nowhere dense graphs[END_REF]).

We show that the comparable box dimension behaves well under the operations of addition of apex vertices, clique-sums, and taking subgraphs. Together with known results on product structure [START_REF] Dujmović | Planar graphs have bounded queue-number[END_REF], this implies the main result of this paper.

▶ Theorem 1. The comparable box dimension of every proper minor-closed class of graphs is finite.

Additionally, we show that classes of graphs with finite comparable box dimension are fractionally treewidth-fragile. This gives arbitrarily precise approximation algorithms for all monotone maximization problems that are expressible in terms of distances between the solution vertices and tractable on graphs of bounded treewidth [START_REF] Dvorák | Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs[END_REF], or expressible in the first-order logic [START_REF] Dvorák | Approximation metatheorem for fractionally treewidth-fragile graphs[END_REF].

Parameters

In this section we bound some basic graph parameters in terms of comparable box dimension. The first result bounds the clique number ω(G) in terms of dim cb (G).

▶ Lemma 2. For any graph G, we have ω(G) ≤ 2 dim cb (G) .
Proof. We may assume that G has bounded comparable box dimension witnessed by a box representation f . To represent any clique A = {a 1 , . . . , a w } in G, the corresponding boxes f (a 1 ), . . . , f (a w ) have pairwise non-empty intersections. Since axis-aligned boxes have the Helly property, there is a point The remaining bounds pertain to the chromatic number χ(G) of a graph G, and two of its variants. An acyclic coloring (resp. star coloring) of a graph G is a proper coloring such that any two color classes induce a forest (resp. star forest, i.e., a forest in which each component is a star). The acyclic chromatic number χ a (G) (resp. star chromatic number χ s (G)) of G is the minimum number of colors in an acyclic (resp. star) coloring of G. We will need the fact that all the variants of the chromatic number are at most exponential in the comparable box dimension; this follows from [START_REF] Dvořák | Sublinear separators in intersection graphs of convex shapes[END_REF], although we include an argument to make the dependence clear.

p ∈ R d contained in f (a 1 ) ∩ • • • ∩ f (a w ).
▶ Lemma 3. For any graph G we have χ(G) ≤ 3 dim cb (G) , χ a (G) ≤ 5 dim cb (G) and χ s (G) ≤ 2 • 9 dim cb (G) .
Proof. We focus on the star chromatic number and note that the chromatic number and the acyclic chromatic number may be bounded similarly. Suppose that G has comparable box dimension d witnessed by a representation f , and let v 1 , . . . , v n be the vertices of G written so that vol(f

(v 1 )) ≥ . . . ≥ vol(f (v n )). Equivalently, we have f (v i ) ⊑ f (v j ) whenever i > j. Now define a greedy coloring c so that c(v i ) is the smallest color such that c(v i ) ̸ = c(v j ) for any j < i for which either v j v i ∈ E(G) or there exists m > j such that v j v m , v m v i ∈ E(G).
Note that this gives a star coloring, since a path on four vertices always contains a 3-vertex subpath of the form v i1 v i2 v i3 such that i 1 < i 2 , i 3 , and our coloring procedure gives distinct colors to vertices forming such a path.

It remains to bound the number of colors used. Suppose we are coloring v i . We shall bound the number of vertices v j such that j < i and such that there exists m > i for which v j v m , v m v i ∈ E(G). Let B be the box obtained by scaling up f (v i ) by a factor of 5 while keeping the same center. Since f (v m ) ⊑ f (v i ) ⊑ f (v j ), there exists a translation B j of f (v i ) contained in f (v j ) ∩ B (see Figure 1). Two boxes B j and B j ′ for j ̸ = j ′ have disjoint interiors since their intersection is contained in the intersection of the touching boxes f (v j ) and f (v j ′ ), and their interiors are also disjoint from f (v i ) ⊂ B. Thus, the number of such indices j is at most vol(B)/ vol(f (v i )) -1 = 5 d -1.

A similar argument shows that the number of indices m such that m < i and v m v i ∈ E(G) is at most 3 d -1. Consequently, the number of indices j < i for which there exists m such that j < m < i and 2 . This means that when choosing the color of v i greedily, we only need to avoid colors of at most (5 is the box whose projection on some first number of dimensions gives the box A, while the projection on the remaining dimensions gives the box B), or specify its projections onto every dimension (and in this case write A[i] for the interval obtained from projecting A on its i th dimension).

v j v m , v m v i ∈ E(G) is at most (3 d -1)
d -1) + (3 d -1) + (3 d -1)
f (v i ) B f (v1) B1 f (v2) B2 f (v3) B3

Vertex addition

Let us start with a simple lemma which says that the addition of a vertex increases the comparable box dimension by at most one. In particular, this implies that dim cb (G) ≤ |V (G)|.

▶ Lemma 4. For any graph G and v ∈ V (G), we have dim cb (G) ≤ dim cb (G -v) + 1. Proof. Let f be a touching representation of G -v by comparable boxes in R d , where d = dim cb (G -v). We define a representation h of G as follows. For each u ∈ V (G) \ {v}, let h(u) = [0, 1] × f (u) if uv ∈ E(G) and h(u) = [1/2, 3/2] × f (u) if uv ̸ ∈ E(G). Let h(v) = [-1, 0] × [-M, M ] × • • • × [-M, M ], where M is chosen large enough so that f (u) ⊆ [-M, M ] × • • • × [-M, M ] for every u ∈ V (G) \ {v}.
Then h is a touching representation of G by comparable boxes in R d+1 . ◀

Strong product

Let G ⊠ H denote the strong product of the graphs G and H, i.e., the graph with vertex set V (G) × V (H) and with distinct vertices (u

f of G ⊠ H in R d G +d H by f ((u, v))[i] = g(u)[i] if i ≤ d G h(v)[i -d G ] if i > d G .
Consider distinct vertices (u, v) and (u ′ , v ′ ) of G⊠H. The boxes g(u) and g(u

′ ) are comparable, say g(u) ⊑ g(u ′ ). Since h(v ′ ) is a translation of h(v), this implies that f ((u, v)) ⊑ f ((u ′ , v ′ )).
Hence, the boxes of the representation f are pairwise comparable.

The boxes of the representations g and h have pairwise disjoint interiors. Hence, if

u ̸ = u ′ , then there exists i ≤ d G such that the interiors of the intervals f ((u, v))[i] = g(u)[i] and f ((u ′ , v ′ ))[i] = g(u ′ )[i] are disjoint; if v ̸ = v ′ , then there exists i ≤ d H such that the interiors of the intervals f ((u, v))[i + d G ] = h(v)[i] and f ((u ′ , v ′ ))[i + d G ] = h(v ′ )[i] are disjoint. Consequently, the interiors of boxes f ((u, v)) and f ((u ′ , v ′ )) are pairwise disjoint. Moreover, if u ̸ = u ′ and uu ′ ̸ ∈ E(G), or if v ̸ = v ′ and vv ′ ̸ ∈ E(G), then the aforementioned intervals (not just their interiors) are disjoint for some i; hence, if (u, v) and (u ′ , v ′ ) are not adjacent in G ⊠ H, then f ((u, v)) ∩ f ((u ′ , v ′ )) = ∅. Therefore, f is a touching representation of a subgraph of G ⊠ H.
Finally, suppose that (u, v) and (u ′ , v ′ ) are adjacent in G ⊠ H. Then there exists a point p G in the intersection of g(u) and g(u ′ ), since u = u ′ or uu ′ ∈ E(G) and g is a touching representation of G; and similarly, there exists a point p H in the intersection of h(v) and

h(v ′ ). Then p G × p H is a point in the intersection of f ((u, v)) and f ((u ′ , v ′ )). Hence, f is indeed a touching representation of G ⊠ H. ◀

Taking a subgraph

The comparable box dimension of a subgraph of a graph G may be larger than dim cb (G) (see the end of this section for an example). However, we show that the comparable box dimension of a subgraph is at most exponential in the comparable box dimension of the whole graph. This is essentially Corollary 25 in [START_REF] Dvořák | Sublinear separators in intersection graphs of convex shapes[END_REF], but since the setting is somewhat different and the construction of [START_REF] Dvořák | Sublinear separators in intersection graphs of convex shapes[END_REF] uses rotated boxes, we provide details of the argument.

▶ Lemma 6. If G is a subgraph of a graph G ′ , then dim cb (G) ≤ dim cb (G ′ ) + 1 2 χ 2 s (G ′ ).
Proof. By removing boxes that represent vertices of G that are not in G ′ , we may assume that

V (G ′ ) = V (G). Let f be a touching representation of G ′ by comparable boxes in R d , where d = dim cb (G ′ ).
Let φ be a star coloring of G ′ using colors {1, . . . , c}, where c = χ s (G ′ ).

For any distinct colors i, j ∈ {1, . . . , c}, let A i,j ⊆ V (G) be the set of vertices u of color i such that there exists a vertex v of color j such that uv ∈ E(G ′ ) \ E(G). For each u ∈ A i,j , let a j (u) denote such a vertex v chosen arbitrarily.

Let us define a representation h by boxes in R d+( c 2 ) by starting from the representation f and, for each pair i < j of colors, adding a dimension d i,j and setting

h(v)[d i,j ] =        [1/3, 4/3] if v ∈ A i,j [-4/3, -1/3] if v ∈ A j,i [-1/2, 1/2] otherwise.
Note that the boxes in this extended representation are comparable, as in the added dimensions, all the boxes have size 1.

Suppose uv ∈ E(G), where φ(u) = i and φ(v) = j and say i < j. We cannot have u ∈ A i,j and v ∈ A j,i , as then a j (u)uva i (v) would be a 4-vertex path in G ′ in colors i and j. Hence, in any added dimension d ′ , we have h

(u)[d ′ ] = [-1/2, 1/2] or h(v)[d ′ ] = [-1/2, 1/2], and thus h(u)[d ′ ] ∩ h(v)[d ′ ] ̸ = ∅.
Since the boxes f (u) and f (v) touch, it follows that the boxes h(u) and h(v) touch as well.

Suppose now that uv

̸ ∈ E(G). If uv ̸ ∈ E(G ′ ), then f (u) is disjoint from f (v), and thus h(u) is disjoint from h(v). Hence, we can assume uv ∈ E(G ′ ) \ E(G), φ(u) = i, φ(v) = j and i < j. Then u ∈ A i,j , v ∈ A j,i , h(u)[d i,j ] = [1/3, 4/3], h(v)[d j,i ] = [-4/3, -1/3], and h(u) ∩ h(v) = ∅.
Consequently, h is a touching representation of G by comparable boxes in dimension

d + c 2 ≤ d + c 2 /2. ◀
Let us now combine Lemmas 3 and 6.

▶ Corollary 7. If G is a subgraph of a graph G ′ , then dim cb (G) ≤ dim cb (G ′ )+2•81 dim cb (G ′ ) ≤ 3 • 81 dim cb (G ′ ) .
An exponential increase in the dimension is unavoidable: we have dim cb (K 2 d ) = d, but the graph obtained from K 2 d by deleting a perfect matching has comparable box dimension 2 d-1 . Indeed, for every pair u, v of non-adjacent vertices there is a specific dimension i such that their boxes span intervals

Clique-sums

A clique-sum of two graphs G 1 and G 2 is obtained from their disjoint union by identifying vertices of a clique in G 1 and a clique of the same size in G 2 and possibly deleting some of the edges of the resulting clique. A full clique-sum is a clique-sum in which we keep all the edges of the resulting clique. The main issue to overcome in obtaining a representation for a (full) clique-sum is that the representations of G 1 and G 2 can be "degenerate". Consider, for example, the case where G 1 is represented by unit squares arranged in a grid; here there is no space to attach G 2 at the cliques formed by four squares intersecting in a single corner. This can be avoided by increasing the dimension, but we need to be careful so that the dimension stays bounded even after an arbitrary number of clique-sums. We thus introduce the notion of clique-sum extendable representations.

▶ Definition 8. Consider a graph G with a distinguished clique C ⋆ , called the root clique of G. A touching representation h of G by (not necessarily comparable) boxes in R d is called C ⋆ -clique-
sum extendable if the following conditions hold for every sufficiently small ε > 0. (vertices) For each u ∈ V (C ⋆ ), there exists a dimension d u , such that:

(v0) d u ̸ = d u ′ for distinct u, u ′ ∈ V (C ⋆ ), (v1) each vertex u ∈ V (C ⋆ ) satisfies h(u)[d u ] = [-1, 0] and h(u)[i] = [0, 1] for any dimension i ̸ = d u , and (v2) each vertex v / ∈ V (C ⋆ ) satisfies h(v) ⊂ [0, 1) d . (cliques) For every clique C of G, there exists a point p(C) ∈ [0, 1) d ∩ v∈V (C) h(v) such that, defining the clique box h ε (C) by setting h ε (C)[i] = [p(C)[i], p(C)[i] + ε]
for every dimension i, the following conditions are satisfied: (c1) For any two cliques

C 1 ̸ = C 2 , h ε (C 1 ) ∩ h ε (C 2 ) = ∅ (equivalently, p(C 1 ) ̸ = p(C 2 )). (c2) A box h(v) intersects h ε (C) if and only if v ∈ V (C)
, and in that case their intersection is a facet of h ε (C) incident to p(C). That is, there exists a dimension i C,v such that for each dimension j,

h(v)[j] ∩ h ε (C)[j] = {p(C)[i C,v ]} if j = i C,v [p(C)[j], p(C)[j] + ε] otherwise.
Note that the root clique can be empty, that is the empty subgraph with no vertices. In that case the clique is denoted ∅. Let dim ext cb (G) be the minimum dimension such that G has an ∅-clique-sum extendable touching representation by comparable boxes.

Let us remark that a clique-sum extendable representation in dimension d implies the existence of such a representation in higher dimensions as well.

▶ Lemma 9. Let G be a graph with a root clique C ⋆ and let h be a C ⋆ -clique-sum extendable touching representation of G by comparable boxes in R d . Then G has such a representation in R d ′ for every d ′ ≥ d.

Proof. It clearly suffices to consider the case that d

′ = d + 1. Note that the (vertices) conditions imply that h(v ′ ) ⊑ h(v) for every v ′ ∈ V (G) \ V (C ⋆ ) and v ∈ V (C ⋆ ). We extend the representation h by setting h(v)[d + 1] = [0, 1] for v ∈ V (C ⋆ ) and h(v)[d + 1] = [0, 1 2 ] for v ∈ V (G) \ V (C ⋆ ). The clique point p(C) of each clique C is extended by setting p(C)[d + 1] = 1 4 .
It is easy to verify that the resulting representation is C ⋆ -clique-sum extendable.

◀

The following lemma ensures that clique-sum extendable representations behave well with respect to full clique-sums. The proof is omitted, but the key strategy is to translate (allowing exchanges of dimensions) and scale h 2 to fit in h ε 1 (C 1 ).

▶ Lemma 10. Consider two graphs G 1 and G 2 , given with a C ⋆ 1 -and a C ⋆ 2 -clique-sum extendable representations h 1 and h 2 by comparable boxes in R d1 and R d2 , respectively. Let G be the graph obtained by performing a full clique-sum of these two graphs on any clique C 1 of G 1 , and on the root clique C ⋆ 2 of G 2 . Then G admits a C ⋆ 1 -clique sum extendable representation h by comparable boxes in R max(d1,d2) .

Moreover, we can pick the root clique at the expense of increasing the dimension by ω(G).

This proof is also omitted, but it is essentially the same as that of Lemma 4.

▶ Lemma 11. For any graph G and any clique C ⋆ , the graph G admits a C ⋆ -clique-sum extendable touching representation by comparable boxes in

R d , for d = |V (C ⋆ )| + dim ext cb (G \ V (C ⋆ )).
The last key lemma that we will need in this section is an upper bound on dim ext cb (G) in terms of dim cb (G) and χ(G).

▶ Lemma 12. For any graph G, dim ext cb (G) ≤ dim cb (G) + χ(G).
Proof. Let h be a touching representation of G by comparable boxes in R d , with d = dim cb (G), and let c be a χ(G)-coloring of G. We start with a slightly modified version of h. We first scale h to fit in (0, 1) d , and for a sufficiently small real α > 0 we increase each box in h by 2α in every dimension, that is we replace h(v

)[i] = [a, b] by [a -α, b + α]
for each vertex v and dimension i. Here, we choose α to be sufficiently small so that the boxes representing non-adjacent vertices remain disjoint, and thus the resulting representation h 1 is an intersection representation of the same graph G. Moreover, observe that for every clique

S o C G 2 0 2 2

38:8 On Comparable Box Dimension

C of G, the intersection I C = v∈V (C) h 1 (v) is a box with non-zero edge lengths. For any clique C of G, let p 1 (C) be a point in the interior of I C different from the points chosen for all other cliques. Now we add χ(G) dimensions to make the representation touching again, and to ensure some space for the clique boxes h ε (C). Formally we define h 2 as

h 2 (u)[i] =            h 1 (u)[i] if i ≤ d [1/5, 3/5] if i > d and c(u) < i -d [0, 2/5] if i > d and c(u) = i -d [2/5, 4/5] otherwise (if c(u) > i -d > 0).
For any clique C of G, let c(C) denote the color set {c(u) | u ∈ V (C)}. We now set

p 2 (C)[i] =        p 1 (C)[i] if i ≤ d 2/5 if i > d and i -d ∈ c(C) 1/2 otherwise.
As h 2 is an extension of h 1 , and as in each dimension j > d, h 2 (v)[j] is an interval of length 2/5 containing the point 2/5 for every vertex v, we have that h 2 is an intersection representation of G by comparable boxes. To prove that it is touching consider two adjacent vertices u and v such that c(u) < c(v), and let us note that h

2 (u)[d + c(u)] = [0, 2/5] and h 2 (v)[d + c(u)] = [2/5, 4/5].
For the ∅-clique-sum extendability, the (vertices) conditions are void. For the (cliques) conditions, since p 1 is chosen to be injective, the mapping p 2 is injective as well, implying that (c1) holds.

Consider now a clique C in G and a vertex v

∈ V (G). If c(v) ̸ ∈ c(C), then h 2 (v)[c(v)+d] = [0, 2/5] and p 2 (C)[c(v) + d] = 1/2, implying that h ε 2 (C) ∩ h 2 (v) = ∅. If c(v) ∈ c(C) but v ̸ ∈ V (C), then letting v ′ ∈ V (C)

be the vertex of color c(v), we have vv ′ ̸ ∈ E(G), and thus

h 1 (v) is disjoint from h 1 (v ′ ). Since p 1 (C) is contained in the interior of h 1 (v ′ ), it follows that h ε 2 (C) ∩ h 2 (v) = ∅. Finally, suppose that v ∈ C. Since p 1 (C) is contained in the interior of h 1 (v), we have h ε 2 (C)[i] ⊂ h 2 (v)[i] for every i ≤ d. For i > d distinct from d + c(v), we have p ε 2 (C)[i] ∈ {2/5, 1/2} and [2/5, 3/5] ⊆ h 2 (v)[i], and thus h ε 2 (C)[i] ⊂ h 2 (v)[i]. For i = d + c(v), we have p ε 2 (C)[i] = 2/5 and h 2 (v)[i] = [0, 2/5], and thus h ε 2 (C)[i] ∩ h 2 (v)[i] = {p ε 2 (C)[i]}. Therefore, (c2) holds. ◀
Together, the preceding lemmas show that comparable box dimension is almost preserved by full clique-sums.

▶ Corollary 13. Let G be a class of graphs of chromatic number at most k. If G ′ is the class of all graphs that can be obtained from G by repeatedly performing full clique-sums, then

dim cb (G ′ ) ≤ dim cb (G) + 2k.
Proof. Suppose a graph G is obtained from G 1 , . . . , G m ∈ G by a sequence of full clique-sums. Without loss of generality, the labelling of the graphs is chosen so that we first perform the full clique-sum on G 1 and G 2 , then on the resulting graph and G 3 , and so on. ) if G has Euler genus at most g. Moreover, for every t, there exists an integer k such that any K t -minor-free graph G is a subgraph of a graph obtained by repeated clique-sums from extended k-tree-grids.

Let us first bound the comparable box dimension of a graph in terms of its Euler genus.

As paths and m-cliques admit touching representations with hypercubes of unit size in R 1 and in R ⌈log 2 m⌉ respectively, by Lemma 5 it suffices to bound the comparable box dimension of k-trees.

▶ Theorem 16. For any k-tree G, dim cb (G) ≤ dim ext cb (G) ≤ k + 1.
Proof. Let H be a complete graph with k +1 vertices and let C ⋆ be a clique of size k in H. By Lemma 10, it suffices to show that H has a C ⋆ -clique-sum extendable touching representation by hypercubes in R k+1 . Let V (C ⋆ ) = {v 1 , . . . , v k }. We construct the representation h so that (v1) holds with d vi = i for each i; this uniquely determines the hypercubes h(v 1 ), . . . ,

h(v k ). For the vertex v k+1 ∈ V (H) \ V (C ⋆ ), we set h(v k+1 ) = [0, 1/2] k+1
. This ensures that the (vertices) conditions holds.

S o C G 2 0 2 2 38:10 On Comparable Box Dimension

For the (cliques) conditions, let us set the point p(C) for every clique C as follows:

p(C)[i] = 0 for every i ≤ k such that v i ∈ C p(C)[i] = 1 4 for every i ≤ k such that v i / ∈ C p(C)[k + 1] = 1 2 if v k+1 ∈ C p(C)[k + 1] = 3 4 if v k+1 / ∈ C By construction, it is clear that for each vertex v ∈ V (H), p(C) ∈ h(v) if and only if v ∈ V (C).
For any two distinct cliques C 1 and C 2 , the points p(C 1 ) and p(C 2 ) are distinct. Indeed, by symmetry we can assume that for some i we have

v i ∈ V (C 1 ) \ V (C 2 ), and this implies that p(C 1 )[i] < p(C 2 )[i].
Hence, the condition (c1) holds.

Consider now a vertex v i and a clique C. As we observed before, if

v i ̸ ∈ V (C), then p(C) ̸ ∈ h(v i ), and thus h ε (C) and h(v i ) are disjoint (for sufficiently small ε > 0). If v i ∈ C, then the definitions ensure that p(C)[i] is equal to the maximum of h(v i )[i], and that for j ̸ = i, p(C)[j] is in h(v i )[j], implying that h(v i )[j] ∩ h ε (C)[j] = [p(C)[j], p(C)[j] + ε] for sufficiently small ε > 0. ◀ The treewidth tw(G) of a graph G is the minimum k such that G is a subgraph of a k-tree.
It is worth noting that the bound on the comparable box dimension of Theorem 16 actually extends to graphs of treewidth at most k (proof omitted).

▶ Corollary 17. Every graph G satisfies dim cb (G) ≤ tw(G) + 1.
As every planar graph G has a touching representation by cubes in R 3 [START_REF] Felsner | Contact representations of planar graphs with cubes[END_REF], we have that dim cb (G) ≤ 3. For graphs with higher Euler genus we can also derive upper bounds. Indeed, combining the previous observation on the representations of paths and K m with Theorem 16, Lemma 5 and Corollary 7 we obtain: ▶ Corollary 18. For every graph G of Euler genus g, there exists a supergraph G ′ of G such that dim cb (G ′ ) ≤ 6 + ⌈log 2 max(2g, 3)⌉. Consequently,

dim cb (G) ≤ 3 • 81 7 • max(2g, 3) log 2 81 .
Similarly, we can deal with proper minor-closed classes.

Proof of Theorem 1. Let G be a proper minor-closed class. Since G is proper, there exists t such that K t ̸ ∈ G. By Theorem 15, there exists k such that every graph in G is a subgraph of a graph obtained by repeated clique-sums from extended k-tree-grids. As we have seen, k-tree-grids have comparable box dimension at most k + 2, and by Lemma 4, extended k-tree-grids have comparable box dimension at most 2k + 2. By Corollary 14, it follows that dim cb (G) ≤ 1250 2k+2 . ◀ Note that the graph obtained from K 2n by deleting a perfect matching has Euler genus Θ(n 2 ) and comparable box dimension n. It follows that the dependence of the comparable box dimension on the Euler genus cannot be subpolynomial (though the degree log 2 81 of the polynomial established in Corollary 18 certainly can be improved). The dependence of the comparable box dimension on the size of the forbidden minor that we established is not explicit, as Theorem 15 is based on the structure theorem of Robertson and Seymour [START_REF] Robertson | Graph Minors. XVI. Excluding a non-planar graph[END_REF]. It would be interesting to prove Theorem 1 without using the structure theorem. Fractional treewidth-fragility Suppose G is a connected planar graph and v is a vertex of G. For an integer k ≥ 2, give each vertex at distance d from v the color d mod k. Then deleting the vertices of any of the k colors results in a graph of treewidth at most 3k. This fact (which follows from the result of Robertson and Seymour [START_REF] Robertson | Graph Minors. III. Planar tree-width[END_REF] on treewidth of planar graphs of bounded radius) is (in the modern terms) the basis of Baker's technique [START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF] for design of approximation algorithms. However, even quite simple graph classes, such as the strong products of three paths [START_REF] Berger | Treewidth of grid subsets[END_REF], do not admit such a coloring where the removal of any color class results in a graph of bounded treewidth. Nonetheless, a fractional version of this coloring concept is still very useful in the design of approximation algorithms [START_REF] Dvorák | Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs[END_REF] and applies to much more general graph classes, including all graph classes with strongly sublinear separators and bounded maximum degree [START_REF] Dvořák | Sublinear separators, fragility and subexponential expansion[END_REF].

A class of graphs G is fractionally treewidth-fragile if there exists a function f such that for every graph G ∈ G and integer k ≥ 2, there exist sets X 1 , . . . , X m ⊆ V (G) such that each vertex belongs to at most m/k of them and tw(G -X i ) ≤ f (k) for every i (equivalently, there exists a probability distribution on the set

{X ⊆ V (G) : tw(G -X) ≤ f (k)} such that Pr[v ∈ X] ≤ 1/k for each v ∈ V (G)).
For example, the class of planar graphs is (fractionally) treewidth-fragile, since we can let X i consist of the vertices of color i -1 in the coloring described at the beginning of the section.

It will be useful to have a different formulation of treewidth for the argument to follow. Recall that a tree decomposition of a graph G is a pair (T, β), where T is a rooted tree and β : V (T ) → 2 V (G) assigns a bag to each of its nodes, such that for each edge uv ∈ E(G), there exists x ∈ V (T ) such that u, v ∈ β(x), and for each vertex v ∈ V (G), the set {x ∈ V (T ) : v ∈ β(x)} is non-empty and induces a connected subtree of T . For nodes x, y ∈ V (T ), we write x ⪯ y if x = y or x is a descendant of y in T . The width of the tree decomposition is the maximum of the sizes of the bags minus 1. The treewidth of a graph is the minimum of the widths of its tree decompositions. Let us remark that the treewidth obtained via this definition coincides with the one via k-trees of Section 4

The purpose of this section is to show that all graph classes of bounded comparable box dimension are fractionally treewidth-fragile. In fact, we prove this result in a more general setting, motivated by concepts from [START_REF] Dvořák | Sublinear separators in intersection graphs of convex shapes[END_REF] and by applications to related representations. The argument is motivated by the idea used in the approximation algorithms for disk graphs by Erlebach et al. [START_REF] Erlebach | Polynomial-time approximation schemes for geometric intersection graphs[END_REF].

For a measurable set A ⊆ R d , let vol(A) denote the Lebesgue measure of A. Given two measurable subsets A and B of R d and a positive integer s, we write A ⊑ s B if for every x ∈ B, there exists a translation A ′ of A such that x ∈ A ′ and vol(A ′ ∩ B) ≥ 1 s vol(A). Note that for two boxes A and B, we have

A ⊑ 1 B if and only if A ⊑ B. An s-comparable envelope representation (ι, ω) of a graph G in R d consists of two functions ι, ω : V (G) → 2 R d such that for some ordering v 1 , . . . , v n of vertices of G, for each i, ω(v i ) is a box, ι(v i ) is a measurable set, and ι(v i ) ⊆ ω(v i ), if i < j, then ω(v j ) ⊑ s ι(v i ), and if i < j and v i v j ∈ E(G), then ω(v j ) ∩ ι(v i ) ̸ = ∅.
We say that the representation has thickness at most t if for every point x ∈ R d , there exist at most

t vertices v ∈ V (G) such that x ∈ ι(v). For example, if f is a touching representation of G by comparable boxes in R d , then (f, f ) is a 1-comparable envelope representation of G in R d of
(k) = O t,s,d k d .
Proof. For a positive integer k, let f (k) = (2ksd + 2) d st. Let (ι, ω) be an s-comparable envelope representation of a graph G in R d of thickness at most t, and let v 1 , . . . , v n be the corresponding ordering of the vertices of G. Let us define ℓ i,j ∈ R + for i = 1, . . . , n and j ∈ {1, . . . , d} as an approximation of ksd|ω(v i )[j]| such that ℓ i-1,j /ℓ i,j is a positive integer. Formally, it is defined by the following process.

Let

ℓ 1,j = ksd|ω(v 1 )[j]|. For i = 2, . . . , n, let ℓ i,j = ℓ i-1,j , if ℓ i-1,j < ksd|ω(v i )[j]
|, and otherwise let ℓ i,j be lowest fraction of ℓ i-1,j that is greater than ksd|ω

(v i )[j]|, formally ℓ i,j = min{ℓ i-1,j /b | b ∈ N + and ℓ i-1,j /b ≥ ksd|ω(v i )[j]|}. Choose x j ∈ [0, ℓ 1,
j ] uniformly at random, and let H i j be the set of hyperplanes in R d consisting of the points whose j-th coordinate is equal to x j + mℓ i,j for some m ∈ Z. As ℓ i,j is a multiple of ℓ i ′ ,j whenever i ≤ i ′ , we have that H i j ⊆ H i ′ j whenever i ≤ i ′ . For i ∈ {1, . . . , n}, the i-grid is H i = d j=1 H i j , and we let the 0-grid H 0 = ∅. Then, as above, we have that

H i ⊆ H i ′ whenever i ≤ i ′ .
Let X ⊆ V (G) consist of the vertices v a ∈ V (G) such that the box ω(v a ) intersects some hyperplane H ∈ H a , that is such that x j + mℓ a,j ∈ ω(v a )[j], for some j ∈ {1, . . . , d} and some m ∈ Z. First, let us argue that Pr

[v a ∈ X] ≤ 1/k. Indeed, the set [0, ℓ 1,j ] ∩ m∈Z (ω(v a )[j] - mℓ a,j ) has measure ℓ1,j ℓa,j • |ω(v a )[j]|,
implying that for fixed j, this happens with probability |ω(v a )[j]|/ℓ a,j . Let a ′ be the largest integer such that a ′ ≤ a and ℓ a ′ ,j < ℓ a ′ -1,j if such an index exists, and a ′ = 1 otherwise; note that ℓ a

,j = ℓ a ′ ,j ≥ ksd|ω(v a ′ )[j]|. Moreover, since ω(v a ) ⊑ s ι(v a ′ ) ⊆ ω(v a ′ ), we have ω(v a )[j] ≤ sω(v a ′ )[j]. Combining these inequalities, |ω(v a )[j]| ℓ a,j ≤ sω(v a ′ )[j] ksd|ω(v a ′ )[j]| = 1 kd .
By the union bound, we conclude that Pr[v a ∈ X] ≤ 1/k. We now bound the treewidth of G -X. For a ≥ 0, an a-cell is a maximal connected

subset of R d \ H∈H a H . A set C ⊆ R d is a cell if it is an a-cell for some a ≥ 0. A cell C is non-empty if there exists v ∈ V (G -X) such that ι(v) ⊆ C.
Note that there exists a rooted tree T whose vertices are the non-empty cells and such that for x, y ∈ V (T ), we have x ⪯ y if and only if x ⊆ y. For each non-empty cell C, define β(C) to be the set of vertices v i ∈ V (G -X) such that ι(v) ∩ C ̸ = ∅ and C is an a-cell for some a ≥ i.

Let us show that (T, β) is a tree decomposition of G -X. For each v j ∈ V (G -X), the j-grid is disjoint from ω(v j ), and thus ι(v j ) ⊆ ω(v j ) ⊂ C for some j-cell C ∈ V (T ) and v j ∈ β(C). Consider now an edge v i v j ∈ E(G -X), where i < j. We have ω(v j ) ∩ ι(v i ) ̸ = ∅, and thus ι(v i ) ∩ C ̸ = ∅ and v i ∈ β(C). Finally, suppose that v j ∈ C ′ for some C ′ ∈ V (T ). Then C ′ is an a-cell for some a ≥ j, and since ι(v j ) ∩ C ′ ̸ = ∅ and ι(v j ) ⊂ C, we conclude that C ′ ⊆ C, and consequently C ′ ⪯ C. Moreover, any cell C ′′ such that C ′ ⪯ C ′′ ⪯ C (and thus C ′ ⊆ C ′′ ⊆ C) is an a ′ -cell for some a ′ ≥ j and ι(v j ) ∩ C ′′ ⊇ ι(v j ) ∩ C ′ ̸ = ∅, which implies that v j ∈ β(C ′′ ). It follows that {C ′ : v j ∈ β(C ′ )} induces a connected subtree of T .

Finally, we bound the width of the decomposition (T, β). Let C be a non-empty cell and let a be maximum number for which C is an a-cell. The proof that (generalizations of) graphs with bounded comparable box dimensions have sublinear separators in [START_REF] Dvořák | Sublinear separators in intersection graphs of convex shapes[END_REF] is indirect; it is established that these graphs have polynomial coloring numbers, which in turn implies they have polynomial expansion, which then gives sublinear separators using the algorithm of Plotkin, Rao, and Smith [START_REF] Plotkin | Shallow excluded minors and improved graph decompositions[END_REF]. The existence of sublinear separators is known to follow more directly from fractional treewidth-fragility. Indeed, since Pr[v ∈ X] ≤ 1/k, there exists X ⊆ V (G) such that tw(G -X) ≤ f

Figure 1

 1 Figure 1 Nearby boxes obstructing colors at vi.

  [a, b] and [c, d] with b < c, while the i th interval of every other box in the representation contains [b, c].

4▶ Theorem 15 .

 15 The strong product structure and minor-closed classesA k-tree is any graph obtained by repeated full clique-sums on cliques of size k from cliques of size at most k + 1. A k-tree-grid is a strong product of a k-tree and a path. An extended k-tree-grid is a graph obtained from a k-tree-grid by adding at most k apex vertices. Dujmović et al.[START_REF] Dujmović | Planar graphs have bounded queue-number[END_REF] proved the following result. Any graph G is a subgraph of the strong product of a k-tree-grid and K m , where k = 3 and m = 3 if G is planar, and k = 4 and m = max(2g, 3

  Then C is an open box with sides of lengths ℓ a,1 , . . . , ℓ a,d . Consider j ∈ {1, . . . , d}:If a = 1, then ℓ a,j = ksd|ω(v a )[j]|. If a > 1 and ℓ a,j = ℓ a-1,j , then ℓ a,j = ℓ a-1,j < 2ksd|ω(v a )[j]| (otherwise ℓ a,j = ℓ a-1,j /b for some integer b ≥ 2).If a > 1 and ℓ a,j < ℓ a-1,j , then ℓ a-1,j ≥ b × ksd|ω(v a )[j]| for some integer b ≥ 2. Now let b be the greatest such integer (that is such that ℓ a-1,j < (b + 1) × ksd|ω(v a )[j]|) and note thatℓ a,j = ℓ a-1,j b < b+1 b ksd|ω(v a )[j]| < 3 2 ksd|ω(v a )[j]|.Hence, in all cases we have ℓ a,j < 2ksd|ω(v a )[j]|. Let C ′ be the box with the same center as C and with |C ′ [j]| = (2ksd + 2)|ω(v a )[j]|. For any v i ∈ β(C) \ {v a }, we have i ≤ a and ι(v i ) ∩ C ̸ = ∅, and since ω(v a ) ⊑ s ι(v i ), there exists a translationB i of ω(v a ) that intersects C ∩ ι(v i ) and such that vol(B i ∩ ι(v i )) ≥ 1 s vol(ω(v a )). Note that as B i intersects C, we have that B i ⊆ C ′ . Using the initial assumption that the representation has thickness at most t, we now havevol(C ′ ) ≥ vol   C ′ ∩ vi∈β(C)\{va} ι(v i ) \{va} B i ∩ ι(v i ) vol(B i ∩ ι(v i )) ≥ vol(ω(v a ))(|β(C)| -1) st .Since vol(C ′ ) = (2ksd + 2) d vol(ω(v a )), it follows that |β(C)| -1 ≤ (2ksd + 2) d st = f (k), as required. ◀

  (k) and |X| ≤ |V (G)|/k. The graph G -X has a balanced separator of size at most tw(G -X) + 1, which combines with X to a balanced separator of size at mostV (G)|/k + f (k) + 1 in G. Optimizing the value of k (choosing it so that V (G)|/k = f (k)),we obtain the following corollary of Theorem 19. ▶ Corollary 20. For positive integers t, s, and d, every graph G with an s-comparable envelope representation in R d of thickness at most t has a sublinear separator of size O t,s,d |V (G)| d d+1 .

  full-dimensional, their interiors each intersect at least one of the 2 d orthants at p. At the same time, it follows from the definition of a touching representation that f (a 1 ), . . . , f (a d ) have pairwise disjoint interiors, and hence w ≤ 2 d . ◀ Note that a clique with 2 d vertices has a touching representation by comparable boxes in R d , where each vertex is a hypercube defined as the Cartesian product of intervals of form [-1, 0] or [0, 1]. From this together with Lemma 2, it follows that dim cb (K 2 d ) = d.

	38:3
	As each box is

G 2 0 2 2 38:4 On Comparable Box Dimension

			2
	vertices, so 2 • 9 d colors suffice.	◀
	3	Operations
	It is clear that, given a touching representation of a graph G, one can easily obtains a
	touching representation by boxes of an induced subgraph H of G by simply deleting the
	boxes corresponding to the vertices in V (G) \ V (H). We shall show that these representations
	also behave nicely under several other basic operations on graphs. To describe the boxes, we
	shall use the Cartesian product × defined among boxes of lower dimension (so that A × B
			S o C

  1 , v 1 ) and (u 2 , v 2 ) adjacent if and only if u 1 is equal to or adjacent to u 2 in G and v 1 is equal to or adjacent to v 2 in H. To obtain a touching representation of G ⊠ H it suffices to take a product of representations of G and H, but the resulting representation may contain incomparable boxes. Indeed, in general dim It suffices to take a product of the two representations. Indeed, consider a touching respresentation g of G by comparable boxes in R d G , with d G = dim cb (G), and the representation h of H. Let us define a representation

cb (G ⊠ H) is not bounded by a function of dim cb (G) and dim cb (H); for example, every star has comparable box dimension at most two, but the strong product of the star K 1,n with itself contains K n,n as an induced subgraph, and thus its comparable box dimension is at least Ω(log n). However, as shown in the following lemma, this issue does not arise if the representation of H consists of translates of a single box; by scaling, we can without loss of generality assume this box is a unit hypercube. ▶ Lemma 5. Consider a graph H having a touching representation h in R d H by axis-aligned hypercubes of unit size. Then for any graph G, the strong product G ⊠ H of these graphs has comparable box dimension at most dim cb (G) + d H .

Proof.

  Let C ⋆ 1 = ∅ and for i = 2, . . . , m, let C ⋆ i be the root clique of G i on which it is glued in the full clique-sum operation. By Lemmas 12 and 11, G i has a C ⋆ i -clique-sum extendable touching representation by comparable boxes in R d , where d = dim cb (G) + 2k. Repeatedly applying Lemma 10, we conclude that dim cb (G) ≤ d. ◀ Putting this corollary together with Lemmas 3 and 6, we obtain the following bounds. Let G be a class of graphs of comparable box dimension at most d. The class G ′ of graphs obtained from G by repeatedly performing full clique-sums has comparable box dimension at most d + 2 • 3 d . The closure of G ′ by taking subgraphs has comparable box dimension at most 1250 d . Proof. The former bound directly follows from Corollary 13 and the bound on the chromatic number from Lemma 3. For the latter, we need to bound the star chromatic number of G ′ . Suppose a graph G is obtained from G 1 , . . . , G m ∈ G by performing full clique-sums. For i = 1, . . . , m, suppose G i has an acyclic coloring φ i by at most k colors. Note that the vertices of any clique get pairwise different colors, and thus by permuting the colors, we can ensure that when we perform the full clique-sum, the vertices that are identified have the same color. Hence, we can define a coloring φ of G such that for each i, the restriction of φ to V (G i ) is equal to φ i . Let C be the union of any two color classes of φ. Then for each i, G G has a star coloring by at most 2k 2 -k colors. Hence, Lemma 3 implies that G ′ has star chromatic number at most 2 • 25 d -5 d . The bound on the comparable box dimension of subgraphs of graphs from G ′ then follows from Lemma 6. ◀

▶ Corollary 14. i [C ∩ V (G i )] is a forest, and since G[C] is obtained from these graphs by full clique-sums, G[C] is also a forest. Hence, φ is an acyclic coloring of G by at most k colors. By

[START_REF] Michael O Albertson | Coloring with no 2-colored p_4's[END_REF]

,

G 2 0 2 2 38:12 On Comparable Box Dimension ▶ Theorem 19.

  thickness at most 2 d . For positive integers t, s, and d, the class of graphs with an s-comparable envelope representation in R d of thickness at most t is fractionally treewidth-fragile, with a function f

	S o C

In their construction h(r) has to be at least 3, and has to tend to +∞.

S o C G 2 0 2 2

Funding Zdeněk Dvořák: Supported by the ERC-CZ project LL2005 (Algorithms and complexity within and beyond bounded expansion) of the Ministry of Education of Czech Republic. Daniel Gonçalves: Supported by the ANR grant GATO ANR-16-CE40-0009. Abhiruk Lahiri: Supported by the ERC-CZ project LL2005 (Algorithms and complexity within and beyond bounded expansion) of the Ministry of Education of Czech Republic.

https://arxiv.org/abs/2203.07686